text: /*
   * Copyright 2012 Google Inc.
   *
   * Use of this source code is governed by a BSD-style license that can be
   * found in the LICENSE file.
   */
  #include "SkAddIntersections.h"
  #include "SkOpCoincidence.h"
  #include "SkOpEdgeBuilder.h"
  #include "SkPathOpsCommon.h"
  #include "SkPathWriter.h"
  #include "SkTSort.h"
  
  SkScalar ScaleFactor(const SkPath& path) {
      static const SkScalar twoTo10 = 1024.f;
      SkScalar largest = 0;
      const SkScalar* oneBounds = &path.getBounds().fLeft;
      for (int index = 0; index < 4; ++index) {
          largest = SkTMax(largest, SkScalarAbs(oneBounds[index]));
      }
      SkScalar scale = twoTo10;
      SkScalar next;
      while ((next = scale * twoTo10) < largest) {
          scale = next;
      }
      return scale == twoTo10 ? SK_Scalar1 : scale;
  }
  
  void ScalePath(const SkPath& path, SkScalar scale, SkPath* scaled) {
      SkMatrix matrix;
      matrix.setScale(scale, scale);
      *scaled = path;
      scaled->transform(matrix);
  }
  
  const SkOpAngle* AngleWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* windingPtr,
          bool* sortablePtr) {
      // find first angle, initialize winding to computed fWindSum
      SkOpSegment* segment = start->segment();
      const SkOpAngle* angle = segment->spanToAngle(start, end);
      if (!angle) {
          *windingPtr = SK_MinS32;
          return nullptr;
      }
      bool computeWinding = false;
      const SkOpAngle* firstAngle = angle;
      bool loop = false;
      bool unorderable = false;
      int winding = SK_MinS32;
      do {
          angle = angle->next();
          if (!angle) {
              return nullptr;
          }
          unorderable |= angle->unorderable();
          if ((computeWinding = unorderable || (angle == firstAngle && loop))) {
              break;    // if we get here, there's no winding, loop is unorderable
          }
          loop |= angle == firstAngle;
          segment = angle->segment();
          winding = segment->windSum(angle);
      } while (winding == SK_MinS32);
      // if the angle loop contains an unorderable span, the angle order may be useless
      // directly compute the winding in this case for each span
      if (computeWinding) {
          firstAngle = angle;
          winding = SK_MinS32;
          do {
              SkOpSpanBase* startSpan = angle->start();
              SkOpSpanBase* endSpan = angle->end();
              SkOpSpan* lesser = startSpan->starter(endSpan);
              int testWinding = lesser->windSum();
              if (testWinding == SK_MinS32) {
                  testWinding = lesser->computeWindSum();
              }
              if (testWinding != SK_MinS32) {
                  segment = angle->segment();
                  winding = testWinding;
              }
              angle = angle->next();
          } while (angle != firstAngle);
      }
      *sortablePtr = !unorderable;
      *windingPtr = winding;
      return angle;
  }
  
  SkOpSegment* FindUndone(SkOpContourHead* contourList, SkOpSpanBase** startPtr,
           SkOpSpanBase** endPtr) {
      SkOpSegment* result;
      SkOpContour* contour = contourList;
      do {
          result = contour->undoneSegment(startPtr, endPtr);
          if (result) {
              return result;
          }
      } while ((contour = contour->next()));
      return nullptr;
  }
  
  SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr,
          SkOpSpanBase** endPtr) {
      while (chase->count()) {
          SkOpSpanBase* span;
          chase->pop(&span);
          SkOpSegment* segment = span->segment();
          *startPtr = span->ptT()->next()->span();
          bool done = true;
          *endPtr = nullptr;
          if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) {
              *startPtr = last->start();
              *endPtr = last->end();
      #if TRY_ROTATE
              *chase->insert(0) = span;
      #else
              *chase->append() = span;
      #endif
              return last->segment();
          }
          if (done) {
              continue;
          }
          // find first angle, initialize winding to computed wind sum
          int winding;
          bool sortable;
          const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable);
          if (!angle) {
              return nullptr;
          }
          if (winding == SK_MinS32) {
              continue;
          }
          int sumWinding SK_INIT_TO_AVOID_WARNING;
          if (sortable) {
              segment = angle->segment();
              sumWinding = segment->updateWindingReverse(angle);
          }
          SkOpSegment* first = nullptr;
          const SkOpAngle* firstAngle = angle;
          while ((angle = angle->next()) != firstAngle) {
              segment = angle->segment();
              SkOpSpanBase* start = angle->start();
              SkOpSpanBase* end = angle->end();
              int maxWinding SK_INIT_TO_AVOID_WARNING;
              if (sortable) {
                  segment->setUpWinding(start, end, &maxWinding, &sumWinding);
              }
              if (!segment->done(angle)) {
                  if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) {
                      first = segment;
                      *startPtr = start;
                      *endPtr = end;
                  }
                  // OPTIMIZATION: should this also add to the chase?
                  if (sortable) {
                      (void) segment->markAngle(maxWinding, sumWinding, angle);
                  }
              }
          }
          if (first) {
         #if TRY_ROTATE
              *chase->insert(0) = span;
         #else
              *chase->append() = span;
         #endif
              return first;
          }
      }
      return nullptr;
  }
  
  bool SortContourList(SkOpContourHead** contourList, bool evenOdd, bool oppEvenOdd) {
      SkTDArray<SkOpContour* > list;
      SkOpContour* contour = *contourList;
      do {
          if (contour->count()) {
              contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd);
              *list.append() = contour;
          }
      } while ((contour = contour->next()));
      int count = list.count();
      if (!count) {
          return false;
      }
      if (count > 1) {
          SkTQSort<SkOpContour>(list.begin(), list.end() - 1);
      }
      contour = list[0];
      SkOpContourHead* contourHead = static_cast<SkOpContourHead*>(contour);
      contour->globalState()->setContourHead(contourHead);
      *contourList = contourHead;
      for (int index = 1; index < count; ++index) {
          SkOpContour* next = list[index];
          contour->setNext(next);
          contour = next;
      }
      contour->setNext(nullptr);
      return true;
  }
  
  class DistanceLessThan {
  public:
      DistanceLessThan(double* distances) : fDistances(distances) { }
      double* fDistances;
      bool operator()(const int one, const int two) {
          return fDistances[one] < fDistances[two];
      }
  };
  
      /*
          check start and end of each contour
          if not the same, record them
          match them up
          connect closest
          reassemble contour pieces into new path
      */
  void Assemble(const SkPathWriter& path, SkPathWriter* simple) {
      SkChunkAlloc allocator(4096);  // FIXME: constant-ize, tune
      SkOpContourHead contour;
      SkOpGlobalState globalState(&contour, &allocator  SkDEBUGPARAMS(false)
                                  SkDEBUGPARAMS(nullptr));
  #if DEBUG_SHOW_TEST_NAME
      SkDebugf("</div>\n");
  #endif
  #if DEBUG_PATH_CONSTRUCTION
      SkDebugf("%s\n", __FUNCTION__);
  #endif
      SkOpEdgeBuilder builder(path, &contour, &globalState);
      builder.finish();
      SkTDArray<const SkOpContour* > runs;  // indices of partial contours
      const SkOpContour* eContour = builder.head();
      do {
          if (!eContour->count()) {
              continue;
          }
          const SkPoint& eStart = eContour->start();
          const SkPoint& eEnd = eContour->end();
  #if DEBUG_ASSEMBLE
          SkDebugf("%s contour", __FUNCTION__);
          if (!SkDPoint::ApproximatelyEqual(eStart, eEnd)) {
              SkDebugf("[%d]", runs.count());
          } else {
              SkDebugf("   ");
          }
          SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n",
                  eStart.fX, eStart.fY, eEnd.fX, eEnd.fY);
  #endif
          if (SkDPoint::ApproximatelyEqual(eStart, eEnd)) {
              eContour->toPath(simple);
              continue;
          }
          *runs.append() = eContour;
      } while ((eContour = eContour->next()));
      int count = runs.count();
      if (count == 0) {
          return;
      }
      SkTDArray<int> sLink, eLink;
      sLink.append(count);
      eLink.append(count);
      int rIndex, iIndex;
      for (rIndex = 0; rIndex < count; ++rIndex) {
          sLink[rIndex] = eLink[rIndex] = SK_MaxS32;
      }
      const int ends = count * 2;  // all starts and ends
      const int entries = (ends - 1) * count;  // folded triangle : n * (n - 1) / 2
      SkTDArray<double> distances;
      distances.append(entries);
      for (rIndex = 0; rIndex < ends - 1; ++rIndex) {
          const SkOpContour* oContour = runs[rIndex >> 1];
          const SkPoint& oPt = rIndex & 1 ? oContour->end() : oContour->start();
          const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2)
                  * ends - rIndex - 1;
          for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) {
              const SkOpContour* iContour = runs[iIndex >> 1];
              const SkPoint& iPt = iIndex & 1 ? iContour->end() : iContour->start();
              double dx = iPt.fX - oPt.fX;
              double dy = iPt.fY - oPt.fY;
              double dist = dx * dx + dy * dy;
              distances[row + iIndex] = dist;  // oStart distance from iStart
          }
      }
      SkTDArray<int> sortedDist;
      sortedDist.append(entries);
      for (rIndex = 0; rIndex < entries; ++rIndex) {
          sortedDist[rIndex] = rIndex;
      }
      SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin()));
      int remaining = count;  // number of start/end pairs
      for (rIndex = 0; rIndex < entries; ++rIndex) {
          int pair = sortedDist[rIndex];
          int row = pair / ends;
          int col = pair - row * ends;
          int thingOne = row < col ? row : ends - row - 2;
          int ndxOne = thingOne >> 1;
          bool endOne = thingOne & 1;
          int* linkOne = endOne ? eLink.begin() : sLink.begin();
          if (linkOne[ndxOne] != SK_MaxS32) {
              continue;
          }
          int thingTwo = row < col ? col : ends - row + col - 1;
          int ndxTwo = thingTwo >> 1;
          bool endTwo = thingTwo & 1;
          int* linkTwo = endTwo ? eLink.begin() : sLink.begin();
          if (linkTwo[ndxTwo] != SK_MaxS32) {
              continue;
          }
          SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]);
          bool flip = endOne == endTwo;
          linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo;
          linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne;
          if (!--remaining) {
              break;
          }
      }
      SkASSERT(!remaining);
  #if DEBUG_ASSEMBLE
      for (rIndex = 0; rIndex < count; ++rIndex) {
          int s = sLink[rIndex];
          int e = eLink[rIndex];
          SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e',
                  s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e);
      }
  #endif
      rIndex = 0;
      do {
          bool forward = true;
          bool first = true;
          int sIndex = sLink[rIndex];
          SkASSERT(sIndex != SK_MaxS32);
          sLink[rIndex] = SK_MaxS32;
          int eIndex;
          if (sIndex < 0) {
              eIndex = sLink[~sIndex];
              sLink[~sIndex] = SK_MaxS32;
          } else {
              eIndex = eLink[sIndex];
              eLink[sIndex] = SK_MaxS32;
          }
          SkASSERT(eIndex != SK_MaxS32);
  #if DEBUG_ASSEMBLE
          SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e',
                      sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e',
                      eIndex < 0 ? ~eIndex : eIndex);
  #endif
          do {
              const SkOpContour* contour = runs[rIndex];
              if (first) {
                  first = false;
                  const SkPoint* startPtr = &contour->start();
                  simple->deferredMove(startPtr[0]);
              }
              if (forward) {
                  contour->toPartialForward(simple);
              } else {
                  contour->toPartialBackward(simple);
              }
  #if DEBUG_ASSEMBLE
              SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex,
                  eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex,
                  sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex));
  #endif
              if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) {
                  simple->close();
                  break;
              }
              if (forward) {
                  eIndex = eLink[rIndex];
                  SkASSERT(eIndex != SK_MaxS32);
                  eLink[rIndex] = SK_MaxS32;
                  if (eIndex >= 0) {
                      SkASSERT(sLink[eIndex] == rIndex);
                      sLink[eIndex] = SK_MaxS32;
                  } else {
                      SkASSERT(eLink[~eIndex] == ~rIndex);
                      eLink[~eIndex] = SK_MaxS32;
                  }
              } else {
                  eIndex = sLink[rIndex];
                  SkASSERT(eIndex != SK_MaxS32);
                  sLink[rIndex] = SK_MaxS32;
                  if (eIndex >= 0) {
                      SkASSERT(eLink[eIndex] == rIndex);
                      eLink[eIndex] = SK_MaxS32;
                  } else {
                      SkASSERT(sLink[~eIndex] == ~rIndex);
                      sLink[~eIndex] = SK_MaxS32;
                  }
              }
              rIndex = eIndex;
              if (rIndex < 0) {
                  forward ^= 1;
                  rIndex = ~rIndex;
              }
          } while (true);
          for (rIndex = 0; rIndex < count; ++rIndex) {
              if (sLink[rIndex] != SK_MaxS32) {
                  break;
              }
          }
      } while (rIndex < count);
  #if DEBUG_ASSEMBLE
      for (rIndex = 0; rIndex < count; ++rIndex) {
         SkASSERT(sLink[rIndex] == SK_MaxS32);
         SkASSERT(eLink[rIndex] == SK_MaxS32);
      }
  #endif
  }
  
  static void calcAngles(SkOpContourHead* contourList) {
      SkOpContour* contour = contourList;
      do {
          contour->calcAngles();
      } while ((contour = contour->next()));
  }
  
  static bool missingCoincidence(SkOpContourHead* contourList) {
      SkOpContour* contour = contourList;
      bool result = false;
      do {
          result |= contour->missingCoincidence();
      } while ((contour = contour->next()));
      return result;
  }
  
  static bool moveMultiples(SkOpContourHead* contourList) {
      SkOpContour* contour = contourList;
      do {
          if (!contour->moveMultiples()) {
              return false;
          }
      } while ((contour = contour->next()));
      return true;
  }
  
  static void moveNearby(SkOpContourHead* contourList) {
      SkOpContour* contour = contourList;
      do {
          contour->moveNearby();
      } while ((contour = contour->next()));
  }
  
  static void sortAngles(SkOpContourHead* contourList) {
      SkOpContour* contour = contourList;
      do {
          contour->sortAngles();
      } while ((contour = contour->next()));
  }
  
  bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidence) {
      SkOpGlobalState* globalState = contourList->globalState();
      DEBUG_COINCIDENCE_HEALTH(contourList, "start");
  #if DEBUG_VALIDATE
      globalState->setPhase(SkOpGlobalState::kIntersecting);
  #endif
  
      // match up points within the coincident runs
      if (!coincidence->addExpanded()) {
          return false;
      }
      DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded");
  #if DEBUG_VALIDATE
      globalState->setPhase(SkOpGlobalState::kWalking);
  #endif
      // combine t values when multiple intersections occur on some segments but not others
      if (!moveMultiples(contourList)) {
          return false;
      }
      DEBUG_COINCIDENCE_HEALTH(contourList, "moveMultiples");
      // move t values and points together to eliminate small/tiny gaps
      (void) moveNearby(contourList);
      DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby");
  #if DEBUG_VALIDATE
      globalState->setPhase(SkOpGlobalState::kIntersecting);
  #endif
      // add coincidence formed by pairing on curve points and endpoints
      coincidence->correctEnds();
      if (!coincidence->addEndMovedSpans()) {
          return false;
      }
      DEBUG_COINCIDENCE_HEALTH(contourList, "addEndMovedSpans");
  
      const int SAFETY_COUNT = 100;  // FIXME: tune
      int safetyHatch = SAFETY_COUNT;
      // look for coincidence present in A-B and A-C but missing in B-C
      while (coincidence->addMissing()) {
          if (!--safetyHatch) {
              SkASSERT(0);  // FIXME: take this out after verifying std tests don't trigger
              return false;
          }
          DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing");
          moveNearby(contourList);
          DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby");
      }
      DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing2");
      // FIXME: only call this if addMissing modified something when returning false
      moveNearby(contourList);
      DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby2");
      // check to see if, loosely, coincident ranges may be expanded
      if (coincidence->expand()) {
          DEBUG_COINCIDENCE_HEALTH(contourList, "expand1");
          coincidence->addMissing();
          DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing2");
          if (!coincidence->addExpanded()) {
              return false;
          }
          DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded2");
          if (!moveMultiples(contourList)) {
              return false;
          }
          DEBUG_COINCIDENCE_HEALTH(contourList, "moveMultiples2");
          moveNearby(contourList);
      }
  #if DEBUG_VALIDATE
      globalState->setPhase(SkOpGlobalState::kWalking);
  #endif
      DEBUG_COINCIDENCE_HEALTH(contourList, "expand2");
      // the expanded ranges may not align -- add the missing spans
      if (!coincidence->addExpanded()) {
          SkASSERT(globalState->debugSkipAssert());
          return false;
      }
      DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded3");
      coincidence->correctEnds();
      if (!coincidence->mark()) {  // mark spans of coincident segments as coincident
          return false;
      }
      DEBUG_COINCIDENCE_HEALTH(contourList, "mark1");
      // look for coincidence lines and curves undetected by intersection
      if (missingCoincidence(contourList)) {
  #if DEBUG_VALIDATE
          globalState->setPhase(SkOpGlobalState::kIntersecting);
  #endif
          DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence1");
          (void) coincidence->expand();
          DEBUG_COINCIDENCE_HEALTH(contourList, "expand3");
          if (!coincidence->addExpanded()) {
              return false;
          }
  #if DEBUG_VALIDATE
          globalState->setPhase(SkOpGlobalState::kWalking);
  #endif
          DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded3");
          if (!coincidence->mark()) {
              return false;
          }
      } else {
          DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence2");
          (void) coincidence->expand();
      }
      DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence3");
  
      (void) coincidence->expand();
  
  #if 0  // under development
      // coincident runs may cross two or more spans, but the opposite spans may be out of order
      if (!coincidence->reorder()) {
        return false;
      }
  #endif
      DEBUG_COINCIDENCE_HEALTH(contourList, "coincidence.reorder");
      SkOpCoincidence overlaps(globalState);
      do {
          SkOpCoincidence* pairs = overlaps.isEmpty() ? coincidence : &overlaps;
          if (!pairs->apply()) {  // adjust the winding value to account for coincident edges
              return false;
          }
          DEBUG_COINCIDENCE_HEALTH(contourList, "pairs->apply");
          // For each coincident pair that overlaps another, when the receivers (the 1st of the pair)
          // are different, construct a new pair to resolve their mutual span
          if (!pairs->findOverlaps(&overlaps)) {
              return false;
          }
          DEBUG_COINCIDENCE_HEALTH(contourList, "pairs->findOverlaps");
      } while (!overlaps.isEmpty());
      calcAngles(contourList);
      sortAngles(contourList);
      if (globalState->angleCoincidence()) {
          (void) missingCoincidence(contourList);
          if (!coincidence->apply()) {
              return false;
          }
      }
  #if DEBUG_COINCIDENCE_VERBOSE
      coincidence->debugShowCoincidence();
  #endif
  #if DEBUG_COINCIDENCE
      coincidence->debugValidate();
  #endif
      SkPathOpsDebug::ShowActiveSpans(contourList);
      return true;
  }
  