// 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;
  
  new Map<Pt, Anchor> anchorMap; // in pseudo-random order (HashSet order)
  //gettable new L<Anchor> anchors;
  new Set<Curve> curves; // also 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 + " and " + end;
    }
    
    // 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; // starting from one
    Pt pt;
    new L<Curve> outgoingCurves;
    new L<Curve> incomingCurves;
    
    *(int *index, Pt *pt) {}
    
    int arity() { ret l(outgoingCurves) + l(incomingCurves); }
    
    toString {
      ret "Anchor " + index + " at " + pt + ", arity " + arity()
        + stringIf(isRingAnchor(), " [arbitrarily chosen ring anchor]");
    }

    // 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;
      if (pointsSeen.contains(p)) true;
      
      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;
        }

        if (!pointsSeen.add(p)) {
          warn("Surprising seen point. Adding as anchor");
          break;
        }
        
        PtBuffer branches = unexploredPointsAround(p);
        
        // line ends or branches - same thing for us
        if (l(branches) != 1) {
          if (debug) print("Branch count: " + l(branches));
          break;
        } else
          p = first(branches);
      }

      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;
    }
      
    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); }
  
  void dropLengthOneCurves {
    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 lesser important anchor into the other one
      if (keepStartAnchor)
        mergeAnchor(curve.end, curve.start);
      else
        mergeAnchor(curve.start, curve.end);
    }
  }
  
  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) {
    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);
      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));
      a2.incomingCurves.add(curve);
    }
    
    anchorMap.remove(a1.pt);
  }
  
  // dev.
  void dropUnnecessaryAnchors {
    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.
      
      // 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);
      
      // 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)));
      addCurve(new Curve(anchor1, anchor2, points));
    }
  }
  
  void addCurve(Curve curve) {
    curves.add(curve);
  }
}