// A "mesh" is a set of points ("anchors") connected through curves.

// An anchor is either

// -the end of a curve

// -an intersection of curves

// -or a randomly chosen point along a curve (type 3)

// A type 3 anchor can be necessary to define an "o" shape

// (because such a shape doesn't have an anchor point per se,

// so we just choose one point along the ring).

// Sometimes however, a type 3 anchor is an artifact of the mesh

// finding process and can be eliminated, reducing the anchor and

// curve count by 1.

srecord noeq G22SkeletonToMesh<Img extends WidthAndHeight>(IImageRegion<Img> region) is Steppable {

  settable bool debug;

  settable bool debugDroppingUnnecessaryAnchors;

  settable bool autoSimplify = true;

  new LinkedHashMap<Pt, Anchor> anchorMap; // sorted by index

  //gettable new L<Anchor> anchors;

  new Set<Curve> curves; // in no particular order

  sclass Curve {

    Anchor start, end;

    OnePathWithOrigin path; // origin = start.pt

    *(Anchor *start, Anchor *end, L<Pt> points) {

      path = new OnePathWithOrigin(points, false);

      start.outgoingCurves.add(this);

      end.incomingCurves.add(this);

    }

    toString {

      ret "Curve of length " + n2(path.nSteps())

        + " connecting " + start?.shortToString() + " and " + end?.shortToString();

    }

    // This counts one of the anchors, but not the other.

    // So if the anchors are right next to each other,

    // the curve's length is 1.

    int length() { ret path.nSteps(); }

    L<Anchor> anchors() { ret ll(start, end); }

  }

  sclass Anchor {

    int index; // every anchor gets a number starting from one

    Pt pt;

    new L<Curve> outgoingCurves;

    new L<Curve> incomingCurves;

    *(int *index, Pt *pt) {}

    int arity() { ret l(outgoingCurves) + l(incomingCurves); }

    S shortToString() {

      ret "Anchor " + index + " at " + pt;

    }

    toString {

      L<Int> connections = sorted(map(connectedToAnchors(), a -> a.index));

      ret shortToString() + ", arity " + arity()

        + stringIf(isRingAnchor(), " [arbitrarily chosen ring anchor]")

        + (empty(connections) ? "" : ", connected to " + joinWithComma(connections));

    }

    Set<Anchor> connectedToAnchors() {

      ret joinSets(

        map(outgoingCurves, c -> c.end),

        map(incomingCurves, c -> c.start));

    }

    // The ring case where we just randomly select an anchor    

    bool isRingAnchor() {

      ret l(outgoingCurves) == 1 && l(incomingCurves) == 1

        && first(outgoingCurves) == first(incomingCurves);

    }

  }

  // TEMPORARY DATA

  ItIt<Pt> regionIterator;

  new L<WorkItem> queue;

  new PtSet pointsSeen;

  // p is a point in 3x3 neighborhood of anchor

  srecord noeq WorkItem(Anchor anchor, Pt p) {}

  public bool step() {

    // first, initialize iterator

    if (regionIterator == null)

      regionIterator = region.pixelIterator();

    // then check queue for work

    if (nempty(queue)) {

      WorkItem work = popLast(queue);

      Pt p = work.p;

      new PtBuffer curvePoints;

      curvePoints.add(work.anchor.pt); // add anchor to path

      Anchor endAnchor = null;

      if (debug) print("Exploring from " + work.anchor.pt + " / " + p);

      while ping (true) {

        if (debug) print("Curve point " + p);

        curvePoints.add(p);

        // did we hit another anchor?

        endAnchor = anchorMap.get(p);

        if (endAnchor != null) {

          if (debug) print("Hit anchor " + endAnchor);

          break;

        }

        // check if we visited this point already

        if (!pointsSeen.add(p)) {

          if (l(curvePoints) == 2)

            true; // It's a 1-pixel curve anyway, just forget it

          else

            // If this is an actual thing, we should make a proper anchor here (splitting existing curves).

            // I don't think it's actually a thing though

            warn("Surprising seen point (" + curvePoints + "). Adding as anchor");

          break;

        }

        PtBuffer branches = unexploredPointsAround(p);

        // line ends or branches - same thing for us, it means our curve ends and we create a new anchor here

        if (l(branches) != 1) {

          if (debug) print("Branch count: " + l(branches));

          break;

        } else

          p = first(branches); // curve continues

      }

      if (endAnchor == null)

        endAnchor = newAnchor(p);

      addCurve(new Curve(work.anchor, endAnchor, curvePoints));

      true;

    }

    // finally look for next point in region

    if (regionIterator.hasNext()) {

      Pt p = regionIterator.next();

      // check if point already seen, otherwise mark as seen

      if (!pointsSeen.add(p)) true;

      // new point - save as anchor

      newAnchor(p);

      true;

    }

    // last step, simplify

    if (autoSimplify) simplify();

    false;

  }

  Anchor newAnchor(Pt p) {  

    Anchor anchor = new(l(anchorMap)+1, p);

    anchorMap.put(p, anchor);

    //anchors.add(anchor);

    // explore in all directions

    for (Pt p2 : unexploredPointsAround(p))

      queue.add(new WorkItem(anchor, p2));

    ret anchor;

  }

  PtBuffer unexploredPointsAround(Pt p) {

    new PtBuffer out;

    for (int dir = 1; dir <= 8; dir++) {

      Pt p2 = onePathDirection(p, dir);

      if (region.contains(p2) && !pointsSeen.contains(p2))

        out.add(p2);

    }

    ret out;

  }

  Cl<Pt> anchorPts() { ret keys(anchorMap); }

  Cl<Anchor> anchors() { ret values(anchorMap); }

  bool simplify() {

    ret 0 != stepAll(combineSteppables_dontDropEnded(

      l0 dropLengthOneCurves,

      l0 dropShortLoops,

      l0 dropUnnecessaryAnchors));

  }

  // drops very short curves connecting a node to itself

  // returns true if anything changed

  bool dropShortLoops() {

    int n = l(curves);

    for (Curve curve : cloneList(curves)) {

      if (curve.start != curve.end) continue;

      if (curve.length() > 3) continue;

      if (debug) print("Removing short loop: " + curve);

      removeCurve(curve);

    }

    ret l(curves) < n;

  }

  // returns true if anything changed

  bool dropLengthOneCurves() {

    int n = l(anchorMap);

    for (Curve curve : cloneList(curves)) {

      if (curve.length() != 1) continue;

      // Decide which anchor to keep

      bool keepStartAnchor = curve.start.arity() >= curve.end.arity();

      // Forget curve

      removeCurve(curve);

      // Merge the less important (defined as: less connected) anchor into the other one

      if (keepStartAnchor)

        mergeAnchor(curve.end, curve.start);

      else

        mergeAnchor(curve.start, curve.end);

    }

    ret l(anchorMap) < n;

  }

  void removeCurve(Curve curve) {

    curves.remove(curve);

    curve.start.outgoingCurves.remove(curve);

    curve.end.incomingCurves.remove(curve);

  }

  // moves a1's connections to a2, deletes a1

  void mergeAnchor(Anchor a1, Anchor a2) {

    if (debug) printVarsInMultipleLines("mergeAnchor", +a1, +a2);

    for (Curve curve : a1.outgoingCurves) {

      // first step is now going from a2 to a1

      curve.path.insertStep(0, ptMinus(a1.pt, a2.pt));

      curve.path.origin(a2.pt);

      curve.start = a2;

      a2.outgoingCurves.add(curve);

    }

    for (Curve curve : a1.incomingCurves) {

      // last step is now going from a1 to a2

      curve.path.addStep(ptMinus(a2.pt, a1.pt));

      curve.end = a2;

      a2.incomingCurves.add(curve);

    }

    anchorMap.remove(a1.pt);

  }

  // returns true if anything changed

  bool dropUnnecessaryAnchors() {

    int n = l(anchorMap);

    for (Anchor anchor : cloneValues(anchorMap)) {

      if (anchor.arity() != 2) continue;

      if (anchor.isRingAnchor()) continue;

      // It's a non-branching anchor sitting on a curve - we can drop it.

      if (debugDroppingUnnecessaryAnchors) print("Dropping " + anchor);

      // This list will have length 2

      L<Curve> curves = concatLists(anchor.incomingCurves, anchor.outgoingCurves);

      // Find the endpoints of the new curve (either 1 or 2 anchors)

      Set<Anchor> anchors = concatMapToSet(curves, c -> c.anchors());

      anchors.remove(this);

      if (debugDroppingUnnecessaryAnchors) printVarsInMultipleLines(+curves, +anchors);

      // Collect points for merged curve

      // Process curve 1, optionally reverse it so it does NOT start at the middle anchor 

      Curve curve1 = first(curves);

      removeCurve(curve1);

      L<Pt> points1 = curve1.path.pointList();

      if (eq(first(points1), anchor.pt)) reverseInPlace(points1);

      // Process curve 2, optionally reverse it so it DOES start at the middle anchor 

      Curve curve2 = second(curves);

      removeCurve(curve2);

      L<Pt> points2 = curve2.path.pointList();

      if (!eq(first(points2), anchor.pt)) reverseInPlace(points2);

      // Drop overlapping point, append points2 to points1

      assertEquals(anchor.pt, popLast(points1));

      L<Pt> points = points1;

      addAll(points, points2);

      Anchor anchor1 = assertNotNull(anchorMap.get(first(points)));

      Anchor anchor2 = assertNotNull(anchorMap.get(last(points)));

      if (debugDroppingUnnecessaryAnchors) printVarsInMultipleLines(+anchor, +anchor1, +anchor2);

      anchorMap.remove(anchor.pt);

      addCurve(new Curve(anchor1, anchor2, points));

    }

    ret l(anchorMap) < n;

  }

  void addCurve(Curve curve) {

    curves.add(curve);

  }

  // Internal structure sanity check 

  void checkArities {

    new MultiMap<Anchor, Curve> outgoing;

    new MultiMap<Anchor, Curve> incoming;

    for (Curve curve : curves) {

      outgoing.add(curve.start, curve);

      if (!anchorMap.containsKey(curve.start.pt))

        fail("Start of curve not found: " + curve);

      incoming.add(curve.end, curve);

      if (!anchorMap.containsKey(curve.end.pt))

        fail("End of curve not found: " + curve);

    }

    for (Anchor anchor : anchors()) {

      assertSetEquals(anchor + " outgoing", outgoing.get(anchor), anchor.outgoingCurves);

      assertSetEquals(anchor + " incoming", incoming.get(anchor), anchor.incomingCurves);

    }

  }

}