/*
 * Copyright 2015 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */
#include "SkOpCoincidence.h"
#include "SkOpSegment.h"
#include "SkPathOpsTSect.h"

// returns true if coincident span's start and end are the same
bool SkCoincidentSpans::collapsed(const SkOpPtT* test) const {
    return (fCoinPtTStart == test && fCoinPtTEnd->contains(test))
        || (fCoinPtTEnd == test && fCoinPtTStart->contains(test))
        || (fOppPtTStart == test && fOppPtTEnd->contains(test))
        || (fOppPtTEnd == test && fOppPtTStart->contains(test));
}

// sets the span's end to the ptT referenced by the previous-next
void SkCoincidentSpans::correctOneEnd(
        const SkOpPtT* (SkCoincidentSpans::* getEnd)() const,
        void (SkCoincidentSpans::*setEnd)(const SkOpPtT* ptT) ) {
    const SkOpPtT* origPtT = (this->*getEnd)();
    const SkOpSpanBase* origSpan = origPtT->span();
    const SkOpSpan* prev = origSpan->prev();
    const SkOpPtT* testPtT = prev ? prev->next()->ptT()
            : origSpan->upCast()->next()->prev()->ptT();
    if (origPtT != testPtT) {
        (this->*setEnd)(testPtT);
    }
}

// FIXME: member pointers have fallen out of favor and can be replaced with
// an alternative approach.
// makes all span ends agree with the segment's spans that define them
void SkCoincidentSpans::correctEnds() {
    this->correctOneEnd(&SkCoincidentSpans::coinPtTStart, &SkCoincidentSpans::setCoinPtTStart);
    this->correctOneEnd(&SkCoincidentSpans::coinPtTEnd, &SkCoincidentSpans::setCoinPtTEnd);
    this->correctOneEnd(&SkCoincidentSpans::oppPtTStart, &SkCoincidentSpans::setOppPtTStart);
    this->correctOneEnd(&SkCoincidentSpans::oppPtTEnd, &SkCoincidentSpans::setOppPtTEnd);
}

/* Please keep this in sync with debugExpand */
// expand the range by checking adjacent spans for coincidence
bool SkCoincidentSpans::expand() {
    bool expanded = false;
    const SkOpSegment* segment = coinPtTStart()->segment();
    const SkOpSegment* oppSegment = oppPtTStart()->segment();
    do {
        const SkOpSpan* start = coinPtTStart()->span()->upCast();
        const SkOpSpan* prev = start->prev();
        const SkOpPtT* oppPtT;
        if (!prev || !(oppPtT = prev->contains(oppSegment))) {
            break;
        }
        double midT = (prev->t() + start->t()) / 2;
        if (!segment->isClose(midT, oppSegment)) {
            break;
        }
        setStarts(prev->ptT(), oppPtT);
        expanded = true;
    } while (true);
    do {
        const SkOpSpanBase* end = coinPtTEnd()->span();
        SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next();
        if (next && next->deleted()) {
            break;
        }
        const SkOpPtT* oppPtT;
        if (!next || !(oppPtT = next->contains(oppSegment))) {
            break;
        }
        double midT = (end->t() + next->t()) / 2;
        if (!segment->isClose(midT, oppSegment)) {
            break;
        }
        setEnds(next->ptT(), oppPtT);
        expanded = true;
    } while (true);
    return expanded;
}

// increase the range of this span
bool SkCoincidentSpans::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
        const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
    bool result = false;
    if (fCoinPtTStart->fT > coinPtTStart->fT || (this->flipped()
            ? fOppPtTStart->fT < oppPtTStart->fT : fOppPtTStart->fT > oppPtTStart->fT)) {
        this->setStarts(coinPtTStart, oppPtTStart);
        result = true;
    }
    if (fCoinPtTEnd->fT < coinPtTEnd->fT || (this->flipped()
            ? fOppPtTEnd->fT > oppPtTEnd->fT : fOppPtTEnd->fT < oppPtTEnd->fT)) {
        this->setEnds(coinPtTEnd, oppPtTEnd);
        result = true;
    }
    return result;
}

// set the range of this span
void SkCoincidentSpans::set(SkCoincidentSpans* next, const SkOpPtT* coinPtTStart,
        const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd
        SkDEBUGPARAMS(int id)) {
    SkASSERT(SkOpCoincidence::Ordered(coinPtTStart, oppPtTStart));
    fNext = next;
    this->setStarts(coinPtTStart, oppPtTStart);
    this->setEnds(coinPtTEnd, oppPtTEnd);
    SkDEBUGCODE(fID = id);
}

// returns true if both points are inside this
bool SkCoincidentSpans::contains(const SkOpPtT* s, const SkOpPtT* e) const {
    if (s->fT > e->fT) {
        SkTSwap(s, e);
    }
    if (s->segment() == fCoinPtTStart->segment()) {
        return fCoinPtTStart->fT <= s->fT && e->fT <= fCoinPtTEnd->fT;
    } else {
        SkASSERT(s->segment() == fOppPtTStart->segment());
        double oppTs = fOppPtTStart->fT;
        double oppTe = fOppPtTEnd->fT;
        if (oppTs > oppTe) {
            SkTSwap(oppTs, oppTe);
        }
        return oppTs <= s->fT && e->fT <= oppTe;
    }
}

// returns the number of segment span's contained by this, or -1 if inconsistent
int SkCoincidentSpans::spanCount() const {
    // most commonly, concidence are one span long; check for that first
    const SkOpSpanBase* start = coinPtTStart()->span();
    const SkOpSpanBase* end = coinPtTEnd()->span();
    int coinIntervals = 0;
    while (start != end) {
        coinIntervals++;
        start = start->upCast()->next();
    }
    const SkOpSpanBase* oppStart = (flipped() ? oppPtTEnd() : oppPtTStart())->span();
    const SkOpSpanBase* oppEnd = (flipped() ? oppPtTStart() : oppPtTEnd())->span();
    int oppIntervals = 0;
    while (oppStart != oppEnd) {
        oppIntervals++;
        oppStart = oppStart->upCast()->next();
    }
    return coinIntervals == oppIntervals ? coinIntervals : -1;
}

// A coincident span is unordered if the pairs of points in the main and opposite curves'
// t values do not ascend or descend. For instance, if a tightly arced quadratic is
// coincident with another curve, it may intersect it out of order.
bool SkCoincidentSpans::ordered() const {
    const SkOpSpanBase* start = this->coinPtTStart()->span();
    const SkOpSpanBase* end = this->coinPtTEnd()->span();
    const SkOpSpanBase* next = start->upCast()->next();
    if (next == end) {
        return true;
    }
    bool flipped = this->flipped();
    const SkOpSegment* oppSeg = this->oppPtTStart()->segment();
    double oppLastT = fOppPtTStart->fT;
    do {
        const SkOpPtT* opp = next->contains(oppSeg);
        if (!opp) {
            SkASSERT(0);  // may assert if coincident span isn't fully processed
            continue;
        }
        if ((oppLastT > opp->fT) != flipped) {
            return false;
        }
        oppLastT = opp->fT;
        if (next == end) {
            break;
        }
        next = next->upCast()->next();
    } while (true);
    return true;
}

// returns true if the point is on a coincident edge, and if it is the start of that edge
bool SkOpCoincidence::edge(const SkOpPtT* test, bool* start) const {
    SkCoincidentSpans* coinRec = fHead;
    if (!coinRec) {
        return false;
    }
    do {
        if (coinRec->coinPtTStart() == test) {
            *start = true;
            return true;
        }
        if (coinRec->coinPtTEnd() == test) {
            *start = false;
            return true;
        }
        if (coinRec->oppPtTStart() == test) {
            *start = !coinRec->flipped();
            return true;
        }
        if (coinRec->coinPtTEnd() == test) {
            *start = coinRec->flipped();
            return true;
        }
    } while ((coinRec = coinRec->next()));
    return false;
}

// if there is an existing pair that overlaps the addition, extend it
bool SkOpCoincidence::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
        const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
    SkCoincidentSpans* test = fHead;
    if (!test) {
        return false;
    }
    const SkOpSegment* coinSeg = coinPtTStart->segment();
    const SkOpSegment* oppSeg = oppPtTStart->segment();
    if (!Ordered(coinPtTStart, oppPtTStart)) {
        SkTSwap(coinSeg, oppSeg);
        SkTSwap(coinPtTStart, oppPtTStart);
        SkTSwap(coinPtTEnd, oppPtTEnd);
        if (coinPtTStart->fT > coinPtTEnd->fT) {
            SkTSwap(coinPtTStart, coinPtTEnd);
            SkTSwap(oppPtTStart, oppPtTEnd);
        }
    }
    double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT);
    SkDEBUGCODE(double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT));
    do {
        if (coinSeg != test->coinPtTStart()->segment()) {
            continue;
        }
        if (oppSeg != test->oppPtTStart()->segment()) {
            continue;
        }
        double oTestMinT = SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT);
        double oTestMaxT = SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT);
        // if debug check triggers, caller failed to check if extended already exists
        SkASSERT(test->coinPtTStart()->fT > coinPtTStart->fT
                || coinPtTEnd->fT > test->coinPtTEnd()->fT
                || oTestMinT > oppMinT || oppMaxT > oTestMaxT);
        if ((test->coinPtTStart()->fT <= coinPtTEnd->fT
                && coinPtTStart->fT <= test->coinPtTEnd()->fT)
                || (oTestMinT <= oTestMaxT && oppMinT <= oTestMaxT)) {
            test->extend(coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
            return true;
        }
    } while ((test = test->next()));
    return false;
}

// verifies that the coincidence hasn't already been added
static void DebugCheckAdd(const SkCoincidentSpans* check, const SkOpPtT* coinPtTStart,
        const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
#if DEBUG_COINCIDENCE
    while (check) {
        SkASSERT(check->coinPtTStart() != coinPtTStart || check->coinPtTEnd() != coinPtTEnd
                || check->oppPtTStart() != oppPtTStart || check->oppPtTEnd() != oppPtTEnd);
        SkASSERT(check->coinPtTStart() != oppPtTStart || check->coinPtTEnd() != oppPtTEnd
                || check->oppPtTStart() != coinPtTStart || check->oppPtTEnd() != coinPtTEnd);
        check = check->next();
    }
#endif
}

// adds a new coincident pair
void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
        SkOpPtT* oppPtTEnd) {
    // OPTIMIZE: caller should have already sorted
    if (!Ordered(coinPtTStart, oppPtTStart)) {
        if (oppPtTStart->fT < oppPtTEnd->fT) {
            this->add(oppPtTStart, oppPtTEnd, coinPtTStart, coinPtTEnd);
        } else {
            this->add(oppPtTEnd, oppPtTStart, coinPtTEnd, coinPtTStart);
        }
        return;
    }
    SkASSERT(Ordered(coinPtTStart, oppPtTStart));
    // choose the ptT at the front of the list to track
    coinPtTStart = coinPtTStart->span()->ptT();
    coinPtTEnd = coinPtTEnd->span()->ptT();
    oppPtTStart = oppPtTStart->span()->ptT();
    oppPtTEnd = oppPtTEnd->span()->ptT();
    SkASSERT(coinPtTStart->fT < coinPtTEnd->fT);
    SkASSERT(oppPtTStart->fT != oppPtTEnd->fT);
    SkOPASSERT(!coinPtTStart->deleted());
    SkOPASSERT(!coinPtTEnd->deleted());
    SkOPASSERT(!oppPtTStart->deleted());
    SkOPASSERT(!oppPtTEnd->deleted());
    DebugCheckAdd(fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
    DebugCheckAdd(fTop, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
    SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate(
            this->globalState()->allocator());
    coinRec->init(SkDEBUGCODE(fGlobalState));
    coinRec->set(this->fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd
            SkDEBUGPARAMS(fGlobalState->nextCoinID()));
    fHead = coinRec;
}

// description below
bool SkOpCoincidence::addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase* testSpan) {
    const SkOpPtT* testPtT = testSpan->ptT();
    const SkOpPtT* stopPtT = testPtT;
    const SkOpSegment* baseSeg = base->segment();
    while ((testPtT = testPtT->next()) != stopPtT) {
        const SkOpSegment* testSeg = testPtT->segment();
        if (testPtT->deleted()) {
            continue;
        }
        if (testSeg == baseSeg) {
            continue;
        }
        if (testPtT->span()->ptT() != testPtT) {
            continue;
        }
        if (this->contains(baseSeg, testSeg, testPtT->fT)) {
            continue;
        }
        // intersect perp with base->ptT() with testPtT->segment()
        SkDVector dxdy = baseSeg->dSlopeAtT(base->t());
        const SkPoint& pt = base->pt();
        SkDLine ray = {{{pt.fX, pt.fY}, {pt.fX + dxdy.fY, pt.fY - dxdy.fX}}};
        SkIntersections i;
        (*CurveIntersectRay[testSeg->verb()])(testSeg->pts(), testSeg->weight(), ray, &i);
        for (int index = 0; index < i.used(); ++index) {
            double t = i[0][index];
            if (!between(0, t, 1)) {
                continue;
            }
            SkDPoint oppPt = i.pt(index);
            if (!oppPt.approximatelyEqual(pt)) {
                continue;
            }
            SkOpSegment* writableSeg = const_cast<SkOpSegment*>(testSeg);
            SkOpPtT* oppStart = writableSeg->addT(t);
            SkOpSpan* writableBase = const_cast<SkOpSpan*>(base);
            oppStart->span()->addOpp(writableBase);
            if (oppStart->deleted()) {
                continue;
            }
            SkOpSegment* coinSeg = base->segment();
            SkOpSegment* oppSeg = oppStart->segment();
            double coinTs, coinTe, oppTs, oppTe;
            if (Ordered(coinSeg, oppSeg)) {
                coinTs = base->t();
                coinTe = testSpan->t();
                oppTs = oppStart->fT;
                oppTe = testPtT->fT;
            } else {
                SkTSwap(coinSeg, oppSeg);
                coinTs = oppStart->fT;
                coinTe = testPtT->fT;
                oppTs = base->t();
                oppTe = testSpan->t();
            }
            if (coinTs > coinTe) {
                SkTSwap(coinTs, coinTe);
                SkTSwap(oppTs, oppTe);
            }
            bool added;
            if (!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &added)) {
                return false;
            }
        }
    }
    return true;
}

// description below
bool SkOpCoincidence::addEndMovedSpans(const SkOpPtT* ptT) {
    FAIL_IF(!ptT->span()->upCastable());
    const SkOpSpan* base = ptT->span()->upCast();
    const SkOpSpan* prev = base->prev();
    FAIL_IF(!prev);
    if (!prev->isCanceled()) {
        if (!this->addEndMovedSpans(base, base->prev())) {
            return false;
        }
    }
    if (!base->isCanceled()) {
        if (!this->addEndMovedSpans(base, base->next())) {
            return false;
        }
    }
    return true;
}

/*  If A is coincident with B and B includes an endpoint, and A's matching point
    is not the endpoint (i.e., there's an implied line connecting B-end and A)
    then assume that the same implied line may intersect another curve close to B.
    Since we only care about coincidence that was undetected, look at the
    ptT list on B-segment adjacent to the B-end/A ptT loop (not in the loop, but
    next door) and see if the A matching point is close enough to form another
    coincident pair. If so, check for a new coincident span between B-end/A ptT loop
    and the adjacent ptT loop.
*/
bool SkOpCoincidence::addEndMovedSpans() {
    SkCoincidentSpans* span = fHead;
    if (!span) {
        return true;
    }
    fTop = span;
    fHead = nullptr;
    do {
        if (span->coinPtTStart()->fPt != span->oppPtTStart()->fPt) {
            FAIL_IF(1 == span->coinPtTStart()->fT);
            bool onEnd = span->coinPtTStart()->fT == 0;
            bool oOnEnd = zero_or_one(span->oppPtTStart()->fT);
            if (onEnd) {
                if (!oOnEnd) {  // if both are on end, any nearby intersect was already found
                    if (!this->addEndMovedSpans(span->oppPtTStart())) {
                        return false;
                    }
                }
            } else if (oOnEnd) {
                if (!this->addEndMovedSpans(span->coinPtTStart())) {
                    return false;
                }
            }
        }
        if (span->coinPtTEnd()->fPt != span->oppPtTEnd()->fPt) {
            bool onEnd = span->coinPtTEnd()->fT == 1;
            bool oOnEnd = zero_or_one(span->oppPtTEnd()->fT);
            if (onEnd) {
                if (!oOnEnd) {
                    if (!this->addEndMovedSpans(span->oppPtTEnd())) {
                        return false;
                    }
                }
            } else if (oOnEnd) {
                if (!this->addEndMovedSpans(span->coinPtTEnd())) {
                    return false;
                }
            }
        }
    } while ((span = span->next()));
    this->restoreHead();
    return true;
}

/* Please keep this in sync with debugAddExpanded */
// for each coincident pair, match the spans
// if the spans don't match, add the missing pt to the segment and loop it in the opposite span
bool SkOpCoincidence::addExpanded() {
    SkCoincidentSpans* coin = this->fHead;
    if (!coin) {
        return true;
    }
    do {
        const SkOpPtT* startPtT = coin->coinPtTStart();
        const SkOpPtT* oStartPtT = coin->oppPtTStart();
        double priorT = startPtT->fT;
        double oPriorT = oStartPtT->fT;
        SkASSERT(startPtT->contains(oStartPtT));
        SkOPASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd()));
        const SkOpSpanBase* start = startPtT->span();
        const SkOpSpanBase* oStart = oStartPtT->span();
        const SkOpSpanBase* end = coin->coinPtTEnd()->span();
        const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span();
        FAIL_IF(oEnd->deleted());
        FAIL_IF(!start->upCastable());
        const SkOpSpanBase* test = start->upCast()->next();
        const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next();
        FAIL_IF(!oTest);
        SkOpSegment* seg = start->segment();
        SkOpSegment* oSeg = oStart->segment();
        while (test != end || oTest != oEnd) {
            const SkOpPtT* containedOpp = test->ptT()->contains(oSeg);
            const SkOpPtT* containedThis = oTest->ptT()->contains(seg);
            if (!containedOpp || !containedThis) {
                // choose the ends, or the first common pt-t list shared by both
                double nextT, oNextT;
                if (containedOpp) {
                    nextT = test->t();
                    oNextT = containedOpp->fT;
                } else if (containedThis) {
                    nextT = containedThis->fT;
                    oNextT = oTest->t();
                } else {
                    // iterate through until a pt-t list found that contains the other
                    const SkOpSpanBase* walk = test;
                    const SkOpPtT* walkOpp;
                    do {
                        FAIL_IF(!walk->upCastable());
                        walk = walk->upCast()->next();
                    } while (!(walkOpp = walk->ptT()->contains(oSeg))
                            && walk != coin->coinPtTEnd()->span());
                    nextT = walk->t();
                    oNextT = walkOpp->fT;
                }
                // use t ranges to guess which one is missing
                double startRange = nextT - priorT;
                FAIL_IF(!startRange);
                double startPart = (test->t() - priorT) / startRange;
                double oStartRange = oNextT - oPriorT;
                FAIL_IF(!oStartRange);
                double oStartPart = (oTest->t() - oPriorT) / oStartRange;
                FAIL_IF(startPart == oStartPart);
                bool addToOpp = !containedOpp && !containedThis ? startPart < oStartPart
                        : !!containedThis;
                bool startOver = false;
                bool success = addToOpp ? oSeg->addExpanded(
                        oPriorT + oStartRange * startPart, test, &startOver)
                        : seg->addExpanded(
                        priorT + startRange * oStartPart, oTest, &startOver);
                FAIL_IF(!success);
                if (startOver) {
                    test = start;
                    oTest = oStart;
                }
                end = coin->coinPtTEnd()->span();
                oEnd = coin->oppPtTEnd()->span();
            }
            if (test != end) {
                FAIL_IF(!test->upCastable());
                priorT = test->t();
                test = test->upCast()->next();
            }
            if (oTest != oEnd) {
                oPriorT = oTest->t();
                oTest = coin->flipped() ? oTest->prev() : oTest->upCast()->next();
                FAIL_IF(!oTest);
            }

        }
    } while ((coin = coin->next()));
    return true;
}

// checks to see if coincidence has already been found
bool SkOpCoincidence::alreadyAdded(const SkCoincidentSpans* check, const SkCoincidentSpans* outer,
        const SkOpPtT* over1s, const SkOpPtT* over1e) const {
    do {
        if (check->oppPtTStart() == outer->coinPtTStart() && check->coinPtTStart() == over1s
                && check->oppPtTEnd() == outer->coinPtTEnd() && check->coinPtTEnd() == over1e) {
            return true;
        }
        if (check->coinPtTStart() == outer->coinPtTStart() && check->oppPtTStart() == over1s
                && check->coinPtTEnd() == outer->coinPtTEnd() && check->oppPtTEnd() == over1e) {
            return true;
        }
        if (check->startEquals(outer->oppPtTStart()->span(), over1s->span())) {
            SkDEBUGCODE(check->debugStartCheck(outer->oppPtTEnd()->span(), over1e->span(),
                    fGlobalState));
            return true;
        }
        if (check->startEquals(over1s->span(), outer->coinPtTStart()->span())) {
            SkDEBUGCODE(check->debugStartCheck(over1e->span(), outer->oppPtTEnd()->span(),
                    fGlobalState));
            return true;
        }
    } while ((check = check->next()));
    return false;
}

    /* Please keep this in sync with debugAddIfMissing() */
bool SkOpCoincidence::addIfMissing(const SkCoincidentSpans* outer, SkOpPtT* over1s,
            SkOpPtT* over1e) {
    SkASSERT(fTop);
    if (this->alreadyAdded(fTop, outer, over1s, over1e)) {
        return false;
    }
    if (fHead && this->alreadyAdded(fHead, outer, over1s, over1e)) {
        return false;
    }
    this->add(outer->coinPtTStart(), outer->coinPtTEnd(), over1s, over1e);
    this->debugValidate();
    return true;
}

// given a t span, map the same range on the coincident span
/*
the curves may not scale linearly, so interpolation may only happen within known points
remap over1s, over1e, cointPtTStart, coinPtTEnd to smallest range that captures over1s
then repeat to capture over1e
*/
double SkOpCoincidence::TRange(const SkOpPtT* overS, double t,
       const SkOpSegment* coinSeg  SkDEBUGPARAMS(const SkOpPtT* overE)) {
    const SkOpSpanBase* work = overS->span();
    const SkOpPtT* foundStart = nullptr;
    const SkOpPtT* foundEnd = nullptr;
    const SkOpPtT* coinStart = nullptr;
    const SkOpPtT* coinEnd = nullptr;
    do {
        const SkOpPtT* contained = work->contains(coinSeg);
        if (!contained) {
            if (work->final()) {
                break;
            }
            continue;
        }
        if (work->t() <= t) {
            coinStart = contained;
            foundStart = work->ptT();
        }
        if (work->t() >= t) {
            coinEnd = contained;
            foundEnd = work->ptT();
            break;
        }
        SkASSERT(work->ptT() != overE);
    } while ((work = work->upCast()->next()));
    if (!coinStart || !coinEnd) {
        return 1;
    }
    // while overS->fT <=t and overS contains coinSeg
    double denom = foundEnd->fT - foundStart->fT;
    double sRatio = denom ? (t - foundStart->fT) / denom : 1;
    return coinStart->fT + (coinEnd->fT - coinStart->fT) * sRatio;
}

// return true if span overlaps existing and needs to adjust the coincident list
bool SkOpCoincidence::checkOverlap(SkCoincidentSpans* check,
        const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
        double coinTs, double coinTe, double oppTs, double oppTe,
        SkTDArray<SkCoincidentSpans*>* overlaps) const {
    if (!Ordered(coinSeg, oppSeg)) {
        if (oppTs < oppTe) {
            return this->checkOverlap(check, oppSeg, coinSeg, oppTs, oppTe, coinTs, coinTe,
                    overlaps);
        }
        return this->checkOverlap(check, oppSeg, coinSeg, oppTe, oppTs, coinTe, coinTs, overlaps);
    }
    bool swapOpp = oppTs > oppTe;
    if (swapOpp) {
        SkTSwap(oppTs, oppTe);
    }
    do {
        if (check->coinPtTStart()->segment() != coinSeg) {
            continue;
        }
        if (check->oppPtTStart()->segment() != oppSeg) {
            continue;
        }
        double checkTs = check->coinPtTStart()->fT;
        double checkTe = check->coinPtTEnd()->fT;
        bool coinOutside = coinTe < checkTs || coinTs > checkTe;
        double oCheckTs = check->oppPtTStart()->fT;
        double oCheckTe = check->oppPtTEnd()->fT;
        if (swapOpp) {
            if (oCheckTs <= oCheckTe) {
                return false;
            }
            SkTSwap(oCheckTs, oCheckTe);
        }
        bool oppOutside = oppTe < oCheckTs || oppTs > oCheckTe;
        if (coinOutside && oppOutside) {
            continue;
        }
        bool coinInside = coinTe <= checkTe && coinTs >= checkTs;
        bool oppInside = oppTe <= oCheckTe && oppTs >= oCheckTs;
        if (coinInside && oppInside) {  // already included, do nothing
            return false;
        }
        *overlaps->append() = check; // partial overlap, extend existing entry
    } while ((check = check->next()));
    return true;
}

/* Please keep this in sync with debugAddIfMissing() */
// note that over1s, over1e, over2s, over2e are ordered
bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over2s,
        double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg, bool* added  
        SkDEBUGPARAMS(const SkOpPtT* over1e) SkDEBUGPARAMS(const SkOpPtT* over2e)) {
    SkASSERT(tStart < tEnd);
    SkASSERT(over1s->fT < over1e->fT);
    SkASSERT(between(over1s->fT, tStart, over1e->fT));
    SkASSERT(between(over1s->fT, tEnd, over1e->fT));
    SkASSERT(over2s->fT < over2e->fT);
    SkASSERT(between(over2s->fT, tStart, over2e->fT));
    SkASSERT(between(over2s->fT, tEnd, over2e->fT));
    SkASSERT(over1s->segment() == over1e->segment());
    SkASSERT(over2s->segment() == over2e->segment());
    SkASSERT(over1s->segment() == over2s->segment());
    SkASSERT(over1s->segment() != coinSeg);
    SkASSERT(over1s->segment() != oppSeg);
    SkASSERT(coinSeg != oppSeg);
    double coinTs, coinTe, oppTs, oppTe;
    coinTs = TRange(over1s, tStart, coinSeg  SkDEBUGPARAMS(over1e));
    coinTe = TRange(over1s, tEnd, coinSeg  SkDEBUGPARAMS(over1e));
    if (coinSeg->collapsed(coinTs, coinTe)) {
        return true;
    }
    oppTs = TRange(over2s, tStart, oppSeg  SkDEBUGPARAMS(over2e));
    oppTe = TRange(over2s, tEnd, oppSeg  SkDEBUGPARAMS(over2e));
    if (oppSeg->collapsed(oppTs, oppTe)) {
        return true;
    }
    if (coinTs > coinTe) {
        SkTSwap(coinTs, coinTe);
        SkTSwap(oppTs, oppTe);
    }
    return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, added);
}

/* Please keep this in sync with debugAddOrOverlap() */
// If this is called by addEndMovedSpans(), a returned false propogates out to an abort.
// If this is called by AddIfMissing(), a returned false indicates there was nothing to add
bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg,
        double coinTs, double coinTe, double oppTs, double oppTe, bool* added) {
    SkTDArray<SkCoincidentSpans*> overlaps;
    FAIL_IF(!fTop);
    if (!this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) {
        return true;
    }
    if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs,
            coinTe, oppTs, oppTe, &overlaps)) {
        return true;
    }
    SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr;
    for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps before continuing
        SkCoincidentSpans* test = overlaps[index];
        if (overlap->coinPtTStart()->fT > test->coinPtTStart()->fT) {
            overlap->setCoinPtTStart(test->coinPtTStart());
        }
        if (overlap->coinPtTEnd()->fT < test->coinPtTEnd()->fT) {
            overlap->setCoinPtTEnd(test->coinPtTEnd());
        }
        if (overlap->flipped()
                ? overlap->oppPtTStart()->fT < test->oppPtTStart()->fT
                : overlap->oppPtTStart()->fT > test->oppPtTStart()->fT) {
            overlap->setOppPtTStart(test->oppPtTStart());
        }
        if (overlap->flipped()
                ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT
                : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) {
            overlap->setOppPtTEnd(test->oppPtTEnd());
        }
        if (!fHead || !this->release(fHead, test)) {
            SkAssertResult(this->release(fTop, test));
        }
    }
    const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg);
    const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg);
    if (overlap && cs && ce && overlap->contains(cs, ce)) {
        return true;
    }
    FAIL_IF(cs == ce && cs);
    const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg);
    const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg);
    if (overlap && os && oe && overlap->contains(os, oe)) {
        return true;
    }
    SkASSERT(!cs || !cs->deleted());
    SkASSERT(!os || !os->deleted());
    SkASSERT(!ce || !ce->deleted());
    SkASSERT(!oe || !oe->deleted());
    const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr;
    const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr;
    FAIL_IF(csExisting && csExisting == ceExisting);
    FAIL_IF(csExisting && (csExisting == ce ||
            csExisting->contains(ceExisting ? ceExisting : ce)));
    FAIL_IF(ceExisting && (ceExisting == cs ||
            ceExisting->contains(csExisting ? csExisting : cs)));
    const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr;
    const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr;
    FAIL_IF(osExisting && osExisting == oeExisting);
    FAIL_IF(osExisting && (osExisting == oe ||
            osExisting->contains(oeExisting ? oeExisting : oe)));
    FAIL_IF(oeExisting && (oeExisting == os ||
            oeExisting->contains(osExisting ? osExisting : os)));
    // extra line in debug code
    this->debugValidate();
    if (!cs || !os) {
        SkOpPtT* csWritable = cs ? const_cast<SkOpPtT*>(cs)
            : coinSeg->addT(coinTs);
        SkOpPtT* osWritable = os ? const_cast<SkOpPtT*>(os)
            : oppSeg->addT(oppTs);
        FAIL_IF(!csWritable || !osWritable);
        csWritable->span()->addOpp(osWritable->span());
        cs = csWritable;
        os = osWritable->active();
        FAIL_IF((ce && ce->deleted()) || (oe && oe->deleted()));
    }
    if (!ce || !oe) {
        SkOpPtT* ceWritable = ce ? const_cast<SkOpPtT*>(ce)
            : coinSeg->addT(coinTe);
        SkOpPtT* oeWritable = oe ? const_cast<SkOpPtT*>(oe)
            : oppSeg->addT(oppTe);
        ceWritable->span()->addOpp(oeWritable->span());
        ce = ceWritable;
        oe = oeWritable;
    }
    this->debugValidate();
    FAIL_IF(cs->deleted());
    FAIL_IF(os->deleted());
    FAIL_IF(ce->deleted());
    FAIL_IF(oe->deleted());
    FAIL_IF(cs->contains(ce) || os->contains(oe));
    bool result = true;
    if (overlap) {
        if (overlap->coinPtTStart()->segment() == coinSeg) {
            result = overlap->extend(cs, ce, os, oe);
        } else {
            if (os->fT > oe->fT) {
                SkTSwap(cs, ce);
                SkTSwap(os, oe);
            }
            result = overlap->extend(os, oe, cs, ce);
        }
#if DEBUG_COINCIDENCE_VERBOSE
        if (result) {
            overlaps[0]->debugShow();
        }
#endif
    } else {
        this->add(cs, ce, os, oe);
#if DEBUG_COINCIDENCE_VERBOSE
        fHead->debugShow();
#endif
    }
    this->debugValidate();
    if (result) {
        *added = true;
    }
    return true;
}

// Please keep this in sync with debugAddMissing()
/* detects overlaps of different coincident runs on same segment */
/* does not detect overlaps for pairs without any segments in common */
// returns true if caller should loop again
bool SkOpCoincidence::addMissing(bool* added) {
    SkCoincidentSpans* outer = fHead;
    *added = false;
    if (!outer) {
        return true;
    }
    fTop = outer;
    fHead = nullptr;
    do {
    // addifmissing can modify the list that this is walking
    // save head so that walker can iterate over old data unperturbed
    // addifmissing adds to head freely then add saved head in the end
        const SkOpPtT* ocs = outer->coinPtTStart();
        SkASSERT(!ocs->deleted());
        const SkOpSegment* outerCoin = ocs->segment();
        SkASSERT(!outerCoin->done());  // if it's done, should have already been removed from list
        const SkOpPtT* oos = outer->oppPtTStart();
        if (oos->deleted()) {
            return true;
        }
        const SkOpSegment* outerOpp = oos->segment();
        SkASSERT(!outerOpp->done());
        SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin);
        SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp);
        SkCoincidentSpans* inner = outer;
        while ((inner = inner->next())) {
            this->debugValidate();
            double overS, overE;
            const SkOpPtT* ics = inner->coinPtTStart();
            SkASSERT(!ics->deleted());
            const SkOpSegment* innerCoin = ics->segment();
            SkASSERT(!innerCoin->done());
            const SkOpPtT* ios = inner->oppPtTStart();
            SkASSERT(!ios->deleted());
            const SkOpSegment* innerOpp = ios->segment();
            SkASSERT(!innerOpp->done());
            SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin);
            SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp);
            if (outerCoin == innerCoin) {
                const SkOpPtT* oce = outer->coinPtTEnd();
                if (oce->deleted()) {
                    return true;
                }
                const SkOpPtT* ice = inner->coinPtTEnd();
                SkASSERT(!ice->deleted());
                if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) {
                    (void) this->addIfMissing(ocs->starter(oce), ics->starter(ice),
                            overS, overE, outerOppWritable, innerOppWritable, added
                            SkDEBUGPARAMS(ocs->debugEnder(oce))
                            SkDEBUGPARAMS(ics->debugEnder(ice)));
                }
            } else if (outerCoin == innerOpp) {
                const SkOpPtT* oce = outer->coinPtTEnd();
                SkASSERT(!oce->deleted());
                const SkOpPtT* ioe = inner->oppPtTEnd();
                SkASSERT(!ioe->deleted());
                if (outerOpp != innerCoin && this->overlap(ocs, oce, ios, ioe, &overS, &overE)) {
                    (void) this->addIfMissing(ocs->starter(oce), ios->starter(ioe),
                            overS, overE, outerOppWritable, innerCoinWritable, added
                            SkDEBUGPARAMS(ocs->debugEnder(oce))
                            SkDEBUGPARAMS(ios->debugEnder(ioe)));
                }
            } else if (outerOpp == innerCoin) {
                const SkOpPtT* ooe = outer->oppPtTEnd();
                SkASSERT(!ooe->deleted());
                const SkOpPtT* ice = inner->coinPtTEnd();
                SkASSERT(!ice->deleted());
                SkASSERT(outerCoin != innerOpp);
                if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) {
                    (void) this->addIfMissing(oos->starter(ooe), ics->starter(ice),
                            overS, overE, outerCoinWritable, innerOppWritable, added
                            SkDEBUGPARAMS(oos->debugEnder(ooe))
                            SkDEBUGPARAMS(ics->debugEnder(ice)));
                }
            } else if (outerOpp == innerOpp) {
                const SkOpPtT* ooe = outer->oppPtTEnd();
                SkASSERT(!ooe->deleted());
                const SkOpPtT* ioe = inner->oppPtTEnd();
                if (ioe->deleted()) {
                    return true;
                }
                SkASSERT(outerCoin != innerCoin);
                if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) {
                    (void) this->addIfMissing(oos->starter(ooe), ios->starter(ioe),
                            overS, overE, outerCoinWritable, innerCoinWritable, added
                            SkDEBUGPARAMS(oos->debugEnder(ooe))
                            SkDEBUGPARAMS(ios->debugEnder(ioe)));
                }
            }
            this->debugValidate();
        }
    } while ((outer = outer->next()));
    this->restoreHead();
    return true;
}

bool SkOpCoincidence::addOverlap(const SkOpSegment* seg1, const SkOpSegment* seg1o,
        const SkOpSegment* seg2, const SkOpSegment* seg2o,
        const SkOpPtT* overS, const SkOpPtT* overE) {
    const SkOpPtT* s1, * e1, * s2, * e2;
    if (!(s1 = overS->find(seg1))) {
        return true;
    }
    if (!(e1 = overE->find(seg1))) {
        return true;
    }
    if (s1 == e1) {
        return true;
    }
    if (approximately_equal_half(s1->fT, e1->fT)) {
        return false;
    }
    if (!s1->starter(e1)->span()->upCast()->windValue()) {
        if (!(s1 = overS->find(seg1o))) {
            return true;
        }
        if (!(e1 = overE->find(seg1o))) {
            return true;
        }
        if (s1 == e1) {
            return true;
        }
        if (!s1->starter(e1)->span()->upCast()->windValue()) {
            return true;
        }
    }
    if (!(s2 = overS->find(seg2))) {
        return true;
    }
    if (!(e2 = overE->find(seg2))) {
        return true;
    }
    if (s2 == e2) {
        return true;
    }
    if (approximately_equal_half(s2->fT, e2->fT)) {
        return false;
    }
    if (!s2->starter(e2)->span()->upCast()->windValue()) {
        if (!(s2 = overS->find(seg2o))) {
            return true;
        }
        if (!(e2 = overE->find(seg2o))) {
            return true;
        }
        if (s2 == e2) {
            return true;
        }
        if (!s2->starter(e2)->span()->upCast()->windValue()) {
            return true;
        }
    }
    if (s1->segment() == s2->segment()) {
        return true;
    }
    if (s1->fT > e1->fT) {
        SkTSwap(s1, e1);
        SkTSwap(s2, e2);
    }
    this->add(s1, e1, s2, e2);
    return true;
}

/* look for pairs of coincidence with no common segments
   if there's no existing coincidence found that matches up the segments, and
   if the pt-t list for one contains the other, create coincident pairs for what's left */
bool SkOpCoincidence::addUncommon() {
    SkCoincidentSpans* outer = fHead;
    if (!outer) {
        return false;
    }
    bool added = false;
    fTop = outer;
    fHead = nullptr;
    do {
        // addifmissing can modify the list that this is walking
        // save head so that walker can iterate over old data unperturbed
        // addifmissing adds to head freely then add saved head in the end
        const SkOpSegment* outerCoin = outer->coinPtTStart()->segment();
        const SkOpSegment* outerOpp = outer->oppPtTStart()->segment();
        if (outerCoin->done() || outerOpp->done()) {
            continue;
        }
        SkCoincidentSpans* inner = outer;
        while ((inner = inner->next())) {
            this->debugValidate();
            const SkOpSegment* innerCoin = inner->coinPtTStart()->segment();
            const SkOpSegment* innerOpp = inner->oppPtTStart()->segment();
            if (innerCoin->done() || innerOpp->done()) {
                continue;
            }
            // check to see if outer span overlaps the inner span
            // look for inner segment in pt-t list
            // if present, and if t values are in coincident range
            // add two pairs of new coincidence
            const SkOpPtT* testS = outer->coinPtTStart()->contains(innerCoin);
            const SkOpPtT* testE = outer->coinPtTEnd()->contains(innerCoin);
            if (testS && testS->fT >= inner->coinPtTStart()->fT
                && testE && testE->fT <= inner->coinPtTEnd()->fT
                && this->testForCoincidence(outer, testS, testE)) {
                added |= this->addIfMissing(outer, testS, testE);
            } else {
                testS = inner->coinPtTStart()->contains(outerCoin);
                testE = inner->coinPtTEnd()->contains(outerCoin);
                if (testS && testS->fT >= outer->coinPtTStart()->fT
                    && testE && testE->fT <= outer->coinPtTEnd()->fT
                    && this->testForCoincidence(inner, testS, testE)) {
                    added |= this->addIfMissing(inner, testS, testE);
                }
            }
        }
    } while ((outer = outer->next()));
    this->restoreHead();
    return added;
}

bool SkOpCoincidence::contains(const SkOpSegment* seg, const SkOpSegment* opp, double oppT) const {
    if (this->contains(fHead, seg, opp, oppT)) {
        return true;
    }
    if (this->contains(fTop, seg, opp, oppT)) {
        return true;
    }
    return false;
}

bool SkOpCoincidence::contains(const SkCoincidentSpans* coin, const SkOpSegment* seg,
        const SkOpSegment* opp, double oppT) const {
    if (!coin) {
        return false;
   }
    do {
        if (coin->coinPtTStart()->segment() == seg && coin->oppPtTStart()->segment() == opp
                && between(coin->oppPtTStart()->fT, oppT, coin->oppPtTEnd()->fT)) {
            return true;
        }
        if (coin->oppPtTStart()->segment() == seg && coin->coinPtTStart()->segment() == opp
                && between(coin->coinPtTStart()->fT, oppT, coin->coinPtTEnd()->fT)) {
            return true;
        }
    } while ((coin = coin->next()));
    return false;
}

bool SkOpCoincidence::contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
        const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const {
    const SkCoincidentSpans* test = fHead;
    if (!test) {
        return false;
    }
    const SkOpSegment* coinSeg = coinPtTStart->segment();
    const SkOpSegment* oppSeg = oppPtTStart->segment();
    if (!Ordered(coinPtTStart, oppPtTStart)) {
        SkTSwap(coinSeg, oppSeg);
        SkTSwap(coinPtTStart, oppPtTStart);
        SkTSwap(coinPtTEnd, oppPtTEnd);
        if (coinPtTStart->fT > coinPtTEnd->fT) {
            SkTSwap(coinPtTStart, coinPtTEnd);
            SkTSwap(oppPtTStart, oppPtTEnd);
        }
    }
    double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT);
    double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT);
    do {
        if (coinSeg != test->coinPtTStart()->segment()) {
            continue;
        }
        if (coinPtTStart->fT < test->coinPtTStart()->fT) {
            continue;
        }
        if (coinPtTEnd->fT > test->coinPtTEnd()->fT) {
            continue;
        }
        if (oppSeg != test->oppPtTStart()->segment()) {
            continue;
        }
        if (oppMinT < SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) {
            continue;
        }
        if (oppMaxT > SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) {
            continue;
        }
        return true;
    } while ((test = test->next()));
    return false;
}

void SkOpCoincidence::correctEnds() {
    SkCoincidentSpans* coin = fHead;
    if (!coin) {
        return;
    }
    do {
        coin->correctEnds();
    } while ((coin = coin->next()));
}

// walk span sets in parallel, moving winding from one to the other
bool SkOpCoincidence::apply() {
    SkCoincidentSpans* coin = fHead;
    if (!coin) {
        return true;
    }
    do {
        SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast();
        if (start->deleted()) {
            continue;
        }
        const SkOpSpanBase* end = coin->coinPtTEnd()->span();
        SkASSERT(start == start->starter(end));
        bool flipped = coin->flipped();
        SkOpSpan* oStart = (flipped ? coin->oppPtTEndWritable()
                : coin->oppPtTStartWritable())->span()->upCast();
        if (oStart->deleted()) {
            continue;
        }
        const SkOpSpanBase* oEnd = (flipped ? coin->oppPtTStart() : coin->oppPtTEnd())->span();
        SkASSERT(oStart == oStart->starter(oEnd));
        SkOpSegment* segment = start->segment();
        SkOpSegment* oSegment = oStart->segment();
        bool operandSwap = segment->operand() != oSegment->operand();
        if (flipped) {
            if (oEnd->deleted()) {
                continue;
            }
            do {
                SkOpSpanBase* oNext = oStart->next();
                if (oNext == oEnd) {
                    break;
                }
                oStart = oNext->upCast();
            } while (true);
        }
        do {
            int windValue = start->windValue();
            int oppValue = start->oppValue();
            int oWindValue = oStart->windValue();
            int oOppValue = oStart->oppValue();
            // winding values are added or subtracted depending on direction and wind type
            // same or opposite values are summed depending on the operand value
            int windDiff = operandSwap ? oOppValue : oWindValue;
            int oWindDiff = operandSwap ? oppValue : windValue;
            if (!flipped) {
                windDiff = -windDiff;
                oWindDiff = -oWindDiff;
            }
            bool addToStart = windValue && (windValue > windDiff || (windValue == windDiff
                    && oWindValue <= oWindDiff));
            if (addToStart ? start->done() : oStart->done()) {
                addToStart ^= true;
            }
            if (addToStart) {
                if (operandSwap) {
                    SkTSwap(oWindValue, oOppValue);
                }
                if (flipped) {
                    windValue -= oWindValue;
                    oppValue -= oOppValue;
                } else {
                    windValue += oWindValue;
                    oppValue += oOppValue;
                }
                if (segment->isXor()) {
                    windValue &= 1;
                }
                if (segment->oppXor()) {
                    oppValue &= 1;
                }
                oWindValue = oOppValue = 0;
            } else {
                if (operandSwap) {
                    SkTSwap(windValue, oppValue);
                }
                if (flipped) {
                    oWindValue -= windValue;
                    oOppValue -= oppValue;
                } else {
                    oWindValue += windValue;
                    oOppValue += oppValue;
                }
                if (oSegment->isXor()) {
                    oWindValue &= 1;
                }
                if (oSegment->oppXor()) {
                    oOppValue &= 1;
                }
                windValue = oppValue = 0;
            }
#if DEBUG_COINCIDENCE
            SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", segment->debugID(),
                    start->debugID(), windValue, oppValue);
            SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", oSegment->debugID(),
                    oStart->debugID(), oWindValue, oOppValue);
#endif
            start->setWindValue(windValue);
            start->setOppValue(oppValue);
            oStart->setWindValue(oWindValue);
            oStart->setOppValue(oOppValue);
            if (!windValue && !oppValue) {
                segment->markDone(start);
            }
            if (!oWindValue && !oOppValue) {
                oSegment->markDone(oStart);
            }
            SkOpSpanBase* next = start->next();
            SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next();
            if (next == end) {
                break;
            }
            if (!next->upCastable()) {
                return false;
            }
            start = next->upCast();
            // if the opposite ran out too soon, just reuse the last span
            if (!oNext || !oNext->upCastable()) {
               oNext = oStart;
            }
            oStart = oNext->upCast();
        } while (true);
    } while ((coin = coin->next()));
    return true;
}

// Please keep this in sync with debugRelease()
bool SkOpCoincidence::release(SkCoincidentSpans* coin, SkCoincidentSpans* remove)  {
    SkCoincidentSpans* head = coin;
    SkCoincidentSpans* prev = nullptr;
    SkCoincidentSpans* next;
    do {
        next = coin->next();
        if (coin == remove) {
            if (prev) {
                prev->setNext(next);
            } else if (head == fHead) {
                fHead = next;
            } else {
                fTop = next;
            }
            break;
        }
        prev = coin;
    } while ((coin = next));
    return coin != nullptr;
}

void SkOpCoincidence::releaseDeleted(SkCoincidentSpans* coin) {
    if (!coin) {
        return;
    }
    SkCoincidentSpans* head = coin;
    SkCoincidentSpans* prev = nullptr;
    SkCoincidentSpans* next;
    do {
        next = coin->next();
        if (coin->coinPtTStart()->deleted()) {
            SkOPASSERT(coin->flipped() ? coin->oppPtTEnd()->deleted() :
                    coin->oppPtTStart()->deleted());
            if (prev) {
                prev->setNext(next);
            } else if (head == fHead) {
                fHead = next;
            } else {
                fTop = next;
            }
        } else {
             SkOPASSERT(coin->flipped() ? !coin->oppPtTEnd()->deleted() :
                    !coin->oppPtTStart()->deleted());
            prev = coin;
        }
    } while ((coin = next));
}

void SkOpCoincidence::releaseDeleted() {
    this->releaseDeleted(fHead);
    this->releaseDeleted(fTop);
}

// Please keep this in sync with debugReorder()
// iterate through all coincident pairs, looking for ranges greater than 1
// if found, see if the opposite pair can match it -- which may require
// reordering the ptT pairs
bool SkOpCoincidence::reorder() {
    SkCoincidentSpans* coin = fHead;
    if (!coin) {
        return true;
    }
    do {
        // most commonly, concidence are one span long; check for that first
        int intervals = coin->spanCount();
        if (intervals <= 0) {
            return false;
        }
        if (1 == intervals) {
#if DEBUG_COINCIDENCE_VERBOSE
            SkASSERT(!coin->debugExpand(nullptr, nullptr));
#endif
            continue;
        }
        coin->expand();  // be all that you can be
        if (coin->spanCount() <= 0) {
            return false;
        }
        // check to see if every span in coin has a mate in opp
        const SkOpSpan* start = coin->coinPtTStart()->span()->upCast();
        bool flipped = coin->flipped();
        const SkOpSpanBase* oppStartBase = coin->oppPtTStart()->span();
        const SkOpSpan* oppStart = flipped ? oppStartBase->prev() : oppStartBase->upCast();
        SkDebugf("", start, oppStart);
    } while ((coin = coin->next()));
    return true;
}

void SkOpCoincidence::restoreHead() {
    SkCoincidentSpans** headPtr = &fHead;
    while (*headPtr) {
        headPtr = (*headPtr)->nextPtr();
    }
    *headPtr = fTop;
    fTop = nullptr;
    // segments may have collapsed in the meantime; remove empty referenced segments
    headPtr = &fHead;
    while (*headPtr) {
        SkCoincidentSpans* test = *headPtr;
        if (test->coinPtTStart()->segment()->done() || test->oppPtTStart()->segment()->done()) {
            *headPtr = test->next();
            continue;
        }
        headPtr = (*headPtr)->nextPtr();
    }
}

// Please keep this in sync with debugExpand()
// expand the range by checking adjacent spans for coincidence
bool SkOpCoincidence::expand() {
    SkCoincidentSpans* coin = fHead;
    if (!coin) {
        return false;
    }
    bool expanded = false;
    do {
        if (coin->expand()) {
            // check to see if multiple spans expanded so they are now identical
            SkCoincidentSpans* test = fHead;
            do {
                if (coin == test) {
                    continue;
                }
                if (coin->coinPtTStart() == test->coinPtTStart()
                        && coin->oppPtTStart() == test->oppPtTStart()) {
                    this->release(fHead, test);
                    break;
                }
            } while ((test = test->next()));
            expanded = true;
        }
    } while ((coin = coin->next()));
    return expanded;
}

bool SkOpCoincidence::findOverlaps(SkOpCoincidence* overlaps) const {
    overlaps->fHead = overlaps->fTop = nullptr;
    SkCoincidentSpans* outer = fHead;
    while (outer) {
        const SkOpSegment* outerCoin = outer->coinPtTStart()->segment();
        const SkOpSegment* outerOpp = outer->oppPtTStart()->segment();
        SkCoincidentSpans* inner = outer;
        while ((inner = inner->next())) {
            const SkOpSegment* innerCoin = inner->coinPtTStart()->segment();
            if (outerCoin == innerCoin) {
                continue;  // both winners are the same segment, so there's no additional overlap
            }
            const SkOpSegment* innerOpp = inner->oppPtTStart()->segment();
            const SkOpPtT* overlapS;
            const SkOpPtT* overlapE;
            if ((outerOpp == innerCoin && SkOpPtT::Overlaps(outer->oppPtTStart(),
                    outer->oppPtTEnd(),inner->coinPtTStart(), inner->coinPtTEnd(), &overlapS,
                    &overlapE))
                    || (outerCoin == innerOpp && SkOpPtT::Overlaps(outer->coinPtTStart(),
                    outer->coinPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(),
                    &overlapS, &overlapE))
                    || (outerOpp == innerOpp && SkOpPtT::Overlaps(outer->oppPtTStart(),
                    outer->oppPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(),
                    &overlapS, &overlapE))) {
                if (!overlaps->addOverlap(outerCoin, outerOpp, innerCoin, innerOpp,
                        overlapS, overlapE)) {
                    return false;
                }
            }
        }
        outer = outer->next();
    }
    return true;
}

// Please keep this in sync with debugRemoveCollapsed()
bool SkOpCoincidence::removeCollapsed() {
    SkCoincidentSpans* coin = fHead;
    if (!coin) {
        return true;
    }
    SkCoincidentSpans** priorPtr = &fHead;
    do {
        if (coin->coinPtTStart() == coin->coinPtTEnd()) {
            return false;
        }
        if (coin->oppPtTStart() == coin->oppPtTEnd()) {
            return false;
        }
        if (coin->coinPtTStart()->collapsed(coin->coinPtTEnd())) {
            *priorPtr = coin->next();
            continue;
        }
        if (coin->oppPtTStart()->collapsed(coin->oppPtTEnd())) {
            *priorPtr = coin->next();
            continue;
        }
        priorPtr = coin->nextPtr();
    } while ((coin = coin->next()));
    return true;
}

void SkOpCoincidence::fixUp(SkOpPtT* deleted, const SkOpPtT* kept) {
    SkOPASSERT(deleted != kept);
    if (fHead) {
        this->fixUp(fHead, deleted, kept);
    }
    if (fTop) {
        this->fixUp(fTop, deleted, kept);
    }
}

void SkOpCoincidence::fixUp(SkCoincidentSpans* coin, SkOpPtT* deleted, const SkOpPtT* kept) {
    SkCoincidentSpans* head = coin;
    do {
        if (coin->coinPtTStart() == deleted) {
            if (coin->coinPtTEnd()->span() == kept->span()) {
                this->release(head, coin);
                continue;
            }
            coin->setCoinPtTStart(kept);
        }
        if (coin->coinPtTEnd() == deleted) {
            if (coin->coinPtTStart()->span() == kept->span()) {
                this->release(head, coin);
                continue;
            }
            coin->setCoinPtTEnd(kept);
       }
        if (coin->oppPtTStart() == deleted) {
            if (coin->oppPtTEnd()->span() == kept->span()) {
                this->release(head, coin);
                continue;
            }
            coin->setOppPtTStart(kept);
        }
        if (coin->oppPtTEnd() == deleted) {
            if (coin->oppPtTStart()->span() == kept->span()) {
                this->release(head, coin);
                continue;
            }
            coin->setOppPtTEnd(kept);
        }
    } while ((coin = coin->next()));
}

// Please keep this in sync with debugMark()
/* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */
bool SkOpCoincidence::mark() {
    SkCoincidentSpans* coin = fHead;
    if (!coin) {
        return true;
    }
    do {
        FAIL_IF(!coin->coinPtTStartWritable()->span()->upCastable());
        SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast();
        SkASSERT(!start->deleted());
        SkOpSpanBase* end = coin->coinPtTEndWritable()->span();
        SkASSERT(!end->deleted());
        SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span();
        FAIL_IF(oStart->deleted());
        SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span();
        SkASSERT(!oEnd->deleted());
        bool flipped = coin->flipped();
        if (flipped) {
            SkTSwap(oStart, oEnd);
        }
        /* coin and opp spans may not match up. Mark the ends, and then let the interior
           get marked as many times as the spans allow */
        start->insertCoincidence(oStart->upCast());
        end->insertCoinEnd(oEnd);
        const SkOpSegment* segment = start->segment();
        const SkOpSegment* oSegment = oStart->segment();
        SkOpSpanBase* next = start;
        SkOpSpanBase* oNext = oStart;
        bool ordered = coin->ordered();
        while ((next = next->upCast()->next()) != end) {
            FAIL_IF(!next->upCastable());
            if (!next->upCast()->insertCoincidence(oSegment, flipped, ordered)) {
                return false;
            }
        }
        while ((oNext = oNext->upCast()->next()) != oEnd) {
            FAIL_IF(!oNext->upCastable());
            if (!oNext->upCast()->insertCoincidence(segment, flipped, ordered)) {
                return false;
            }
        }
    } while ((coin = coin->next()));
    return true;
}

// Please keep in sync with debugMarkCollapsed()
void SkOpCoincidence::markCollapsed(SkCoincidentSpans* coin, SkOpPtT* test) {
    SkCoincidentSpans* head = coin;
    while (coin) {
        if (coin->collapsed(test)) {
            if (zero_or_one(coin->coinPtTStart()->fT) && zero_or_one(coin->coinPtTEnd()->fT)) {
                coin->coinPtTStartWritable()->segment()->markAllDone();
            }
            if (zero_or_one(coin->oppPtTStart()->fT) && zero_or_one(coin->oppPtTEnd()->fT)) {
                coin->oppPtTStartWritable()->segment()->markAllDone();
            }
            this->release(head, coin);
        }
        coin = coin->next();
    }
}

// Please keep in sync with debugMarkCollapsed()
void SkOpCoincidence::markCollapsed(SkOpPtT* test) {
    markCollapsed(fHead, test);
    markCollapsed(fTop, test);
}

bool SkOpCoincidence::Ordered(const SkOpSegment* coinSeg, const SkOpSegment* oppSeg) {
    if (coinSeg->verb() < oppSeg->verb()) {
        return true;
    }
    if (coinSeg->verb() > oppSeg->verb()) {
        return false;
    }
    int count = (SkPathOpsVerbToPoints(coinSeg->verb()) + 1) * 2;
    const SkScalar* cPt = &coinSeg->pts()[0].fX;
    const SkScalar* oPt = &oppSeg->pts()[0].fX;
    for (int index = 0; index < count; ++index) {
        if (*cPt < *oPt) {
            return true;
        }
        if (*cPt > *oPt) {
            return false;
        }
        ++cPt;
        ++oPt;
    }
    return true;
}

bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e,
        const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const {
    SkASSERT(coin1s->segment() == coin2s->segment());
    *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->fT));
    *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->fT));
    return *overS < *overE;
}

// Commented-out lines keep this in sync with debugRelease()
void SkOpCoincidence::release(const SkOpSegment* deleted) {
    SkCoincidentSpans* coin = fHead;
    if (!coin) {
        return;
    }
    do {
        if (coin->coinPtTStart()->segment() == deleted
                || coin->coinPtTEnd()->segment() == deleted
                || coin->oppPtTStart()->segment() == deleted
                || coin->oppPtTEnd()->segment() == deleted) {
            this->release(fHead, coin);
        }
    } while ((coin = coin->next()));
}

bool SkOpCoincidence::testForCoincidence(const SkCoincidentSpans* outer, const SkOpPtT* testS,
        const SkOpPtT* testE) const {
    return testS->segment()->testForCoincidence(testS, testE, testS->span(),
            testE->span(), outer->coinPtTStart()->segment());
}