text: /*
   * Copyright 2013 Google Inc.
   *
   * Use of this source code is governed by a BSD-style license that can be
   * found in the LICENSE file.
   */
  #ifndef SkOpContour_DEFINED
  #define SkOpContour_DEFINED
  
  #include "SkOpSegment.h"
  #include "SkTArray.h"
  
  #if defined(SK_DEBUG) || !FORCE_RELEASE
  #include "SkThread.h"
  #endif
  
  class SkIntersections;
  class SkOpContour;
  class SkPathWriter;
  
  struct SkCoincidence {
      SkOpContour* fOther;
      int fSegments[2];
      double fTs[2][2];
      SkPoint fPts[2][2];
      int fNearly[2];
  };
  
  class SkOpContour {
  public:
      SkOpContour() {
          reset();
  #if defined(SK_DEBUG) || !FORCE_RELEASE
          fID = sk_atomic_inc(&SkPathOpsDebug::gContourID);
  #endif
      }
  
      bool operator<(const SkOpContour& rh) const {
          return fBounds.fTop == rh.fBounds.fTop
                  ? fBounds.fLeft < rh.fBounds.fLeft
                  : fBounds.fTop < rh.fBounds.fTop;
      }
  
      bool addCoincident(int index, SkOpContour* other, int otherIndex,
                         const SkIntersections& ts, bool swap);
      void addCoincidentPoints();
  
      void addCross(const SkOpContour* crosser) {
  #ifdef DEBUG_CROSS
          for (int index = 0; index < fCrosses.count(); ++index) {
              SkASSERT(fCrosses[index] != crosser);
          }
  #endif
          fCrosses.push_back(crosser);
      }
  
      void addCubic(const SkPoint pts[4]) {
          fSegments.push_back().addCubic(pts, fOperand, fXor);
          fContainsCurves = fContainsCubics = true;
      }
  
      int addLine(const SkPoint pts[2]) {
          fSegments.push_back().addLine(pts, fOperand, fXor);
          return fSegments.count();
      }
  
      void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) {
          fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex);
      }
  
      bool addPartialCoincident(int index, SkOpContour* other, int otherIndex,
                         const SkIntersections& ts, int ptIndex, bool swap);
  
      int addQuad(const SkPoint pts[3]) {
          fSegments.push_back().addQuad(pts, fOperand, fXor);
          fContainsCurves = true;
          return fSegments.count();
      }
  
      int addT(int segIndex, SkOpContour* other, int otherIndex, const SkPoint& pt, double newT) {
          setContainsIntercepts();
          return fSegments[segIndex].addT(&other->fSegments[otherIndex], pt, newT);
      }
  
      int addSelfT(int segIndex, const SkPoint& pt, double newT) {
          setContainsIntercepts();
          return fSegments[segIndex].addSelfT(pt, newT);
      }
  
      void align(const SkOpSegment::AlignedSpan& aligned, bool swap, SkCoincidence* coincidence);
      void alignCoincidence(const SkOpSegment::AlignedSpan& aligned,
              SkTArray<SkCoincidence, true>* coincidences);
  
      void alignCoincidence(const SkOpSegment::AlignedSpan& aligned) {
          alignCoincidence(aligned, &fCoincidences);
          alignCoincidence(aligned, &fPartialCoincidences);
      }
  
      void alignMultiples(SkTDArray<SkOpSegment::AlignedSpan>* aligned) {
          int segmentCount = fSegments.count();
          for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
              SkOpSegment& segment = fSegments[sIndex];
              if (segment.hasMultiples()) {
                  segment.alignMultiples(aligned);
              }
          }
      }
  
      void alignTPt(int segmentIndex, const SkOpContour* other, int otherIndex,
                    bool swap, int tIndex, SkIntersections* ts, SkPoint* point) const;
  
      const SkPathOpsBounds& bounds() const {
          return fBounds;
      }
  
      bool calcAngles();
      void calcCoincidentWinding();
      void calcPartialCoincidentWinding();
  
      void checkDuplicates() {
          int segmentCount = fSegments.count();
          for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
              SkOpSegment& segment = fSegments[sIndex];
              if (segment.count() > 2) {
                  segment.checkDuplicates();
              }
          }
      }
  
      void checkEnds() {
          if (!fContainsCurves) {
              return;
          }
          int segmentCount = fSegments.count();
          for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
              SkOpSegment* segment = &fSegments[sIndex];
              if (segment->verb() == SkPath::kLine_Verb) {
                  continue;
              }
              if (segment->done()) {
                  continue;   // likely coincident, nothing to do
              }
              segment->checkEnds();
          }
      }
  
      void checkMultiples() {
          int segmentCount = fSegments.count();
          for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
              SkOpSegment& segment = fSegments[sIndex];
              if (segment.count() > 2) {
                  segment.checkMultiples();
                  fMultiples |= segment.hasMultiples();
              }
          }
      }
  
      void checkSmall() {
          int segmentCount = fSegments.count();
          for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
              SkOpSegment& segment = fSegments[sIndex];
              // OPTIMIZATION : skip segments that are done?
              if (segment.hasSmall()) {
                  segment.checkSmall();
              }
          }
      }
  
      // if same point has different T values, choose a common T
      void checkTiny() {
          int segmentCount = fSegments.count();
          if (segmentCount <= 2) {
              return;
          }
          for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
              SkOpSegment& segment = fSegments[sIndex];
              if (segment.hasTiny()) {
                  segment.checkTiny();
              }
          }
      }
  
      void complete() {
          setBounds();
          fContainsIntercepts = false;
      }
  
      bool containsCubics() const {
          return fContainsCubics;
      }
  
      bool crosses(const SkOpContour* crosser) const {
          for (int index = 0; index < fCrosses.count(); ++index) {
              if (fCrosses[index] == crosser) {
                  return true;
              }
          }
          return false;
      }
  
      bool done() const {
          return fDone;
      }
  
      const SkPoint& end() const {
          const SkOpSegment& segment = fSegments.back();
          return segment.pts()[SkPathOpsVerbToPoints(segment.verb())];
      }
  
      void fixOtherTIndex() {
          int segmentCount = fSegments.count();
          for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
              fSegments[sIndex].fixOtherTIndex();
          }
      }
  
      bool hasMultiples() const {
          return fMultiples;
      }
  
      void joinCoincidence() {
          joinCoincidence(fCoincidences, false);
          joinCoincidence(fPartialCoincidences, true);
      }
  
      SkOpSegment* nonVerticalSegment(int* start, int* end);
  
      bool operand() const {
          return fOperand;
      }
  
      void reset() {
          fSegments.reset();
          fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
          fContainsCurves = fContainsCubics = fContainsIntercepts = fDone = fMultiples = false;
      }
  
      void resolveNearCoincidence();
  
      SkTArray<SkOpSegment>& segments() {
          return fSegments;
      }
  
      void setContainsIntercepts() {
          fContainsIntercepts = true;
      }
  
      void setOperand(bool isOp) {
          fOperand = isOp;
      }
  
      void setOppXor(bool isOppXor) {
          fOppXor = isOppXor;
          int segmentCount = fSegments.count();
          for (int test = 0; test < segmentCount; ++test) {
              fSegments[test].setOppXor(isOppXor);
          }
      }
  
      void setXor(bool isXor) {
          fXor = isXor;
      }
  
      void sortAngles();
      void sortSegments();
  
      const SkPoint& start() const {
          return fSegments.front().pts()[0];
      }
  
      void toPath(SkPathWriter* path) const;
  
      void toPartialBackward(SkPathWriter* path) const {
          int segmentCount = fSegments.count();
          for (int test = segmentCount - 1; test >= 0; --test) {
              fSegments[test].addCurveTo(1, 0, path, true);
          }
      }
  
      void toPartialForward(SkPathWriter* path) const {
          int segmentCount = fSegments.count();
          for (int test = 0; test < segmentCount; ++test) {
              fSegments[test].addCurveTo(0, 1, path, true);
          }
      }
  
      void topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY, SkOpSegment** topStart);
      SkOpSegment* undoneSegment(int* start, int* end);
  
      int updateSegment(int index, const SkPoint* pts) {
          SkOpSegment& segment = fSegments[index];
          segment.updatePts(pts);
          return SkPathOpsVerbToPoints(segment.verb()) + 1;
      }
  
  #if DEBUG_TEST
      SkTArray<SkOpSegment>& debugSegments() {
          return fSegments;
      }
  #endif
  
  #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
      void debugShowActiveSpans() {
          for (int index = 0; index < fSegments.count(); ++index) {
              fSegments[index].debugShowActiveSpans();
          }
      }
  #endif
  
  #if DEBUG_SHOW_WINDING
      int debugShowWindingValues(int totalSegments, int ofInterest);
      static void debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList);
  #endif
  
      // available to test routines only
      void dump() const;
      void dumpAngles() const;
      void dumpCoincidence(const SkCoincidence& ) const;
      void dumpCoincidences() const;
      void dumpPt(int ) const;
      void dumpPts() const;
      void dumpSpan(int ) const;
      void dumpSpans() const;
  
  private:
      void alignPt(int index, SkPoint* point, int zeroPt) const;
      int alignT(bool swap, int tIndex, SkIntersections* ts) const;
      void calcCommonCoincidentWinding(const SkCoincidence& );
      void checkCoincidentPair(const SkCoincidence& oneCoin, int oneIdx,
                               const SkCoincidence& twoCoin, int twoIdx, bool partial);
      void joinCoincidence(const SkTArray<SkCoincidence, true>& , bool partial);
      void setBounds();
  
      SkTArray<SkOpSegment> fSegments;
      SkTArray<SkOpSegment*, true> fSortedSegments;
      int fFirstSorted;
      SkTArray<SkCoincidence, true> fCoincidences;
      SkTArray<SkCoincidence, true> fPartialCoincidences;
      SkTArray<const SkOpContour*, true> fCrosses;
      SkPathOpsBounds fBounds;
      bool fContainsIntercepts;  // FIXME: is this used by anybody?
      bool fContainsCubics;
      bool fContainsCurves;
      bool fDone;
      bool fMultiples;  // set if some segment has multiple identical intersections with other curves
      bool fOperand;  // true for the second argument to a binary operator
      bool fXor;
      bool fOppXor;
  #if defined(SK_DEBUG) || !FORCE_RELEASE
      int debugID() const { return fID; }
      int fID;
  #else
      int debugID() const { return -1; }
  #endif
  };
  
  #endif
  