// 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.

// G22Mesh has identity-based equality although it would be possible
// to define a value-based equality function.

persistable sclass G22Mesh > Meta is MakesBufferedImage {
  new LinkedHashMap<Pt, Anchor> anchorMap; // sorted by index
  gettable new LinkedHashSet<Curve> curves;

  // cached signature
  S cachedSignature;
  
  persistable sclass Curve {
    gettable Anchor start;
    gettable Anchor end;
    gettable OnePathWithOrigin path; // origin = start.pt
    
    *(Anchor start, Anchor end, L<Pt> points) {
      this(start, end, new OnePathWithOrigin(points, false));
    }
    
    *(Anchor *start, Anchor *end, OnePathWithOrigin *path) {
      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); }
    
    bool connectedTo(Anchor a) {
      ret start == a || end == a;
    }
    
    Anchor anchor(bool endAnchor) { ret endAnchor ? end : start; }
    
    Anchor anchorOpposite(Anchor a) {
      ret a == start ? end : a == end ? start : null;
    }
  } // end of Curve
  
  persistable sclass Anchor {
    int index; // every anchor gets a number starting from one
    gettable 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<Curve> curves() {
      ret joinSets(outgoingCurves, incomingCurves);
    }
    
    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);
    }
  } // end of Anchor
  
  Cl<Pt> anchorPts() { ret keys(anchorMap); }
  Cl<Anchor> anchors() { ret values(anchorMap); }
  int nAnchors() { ret l(anchorMap); }
  L<Anchor> anchorList() { ret valuesList(anchorMap); }
  Anchor getAnchor(Pt p) { ret anchorMap.get(p); }
  Anchor getAnchor(int idx) { ret anchorList().get(idx); }
  
  // 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);
    }
  }
  
  Anchor newAnchor aka addAnchor(Pt p) {  
    Anchor anchor = new(l(anchorMap)+1, p);
    anchorMap.put(p, anchor);
    _invalidateSignature();
    ret anchor;
  }
  
  void removeAnchor(Anchor anchor) {
    anchorMap.remove(anchor.pt);
  }
  
  Curve addCurve(Curve curve) {
    curves.add(curve);
    _invalidateSignature();
    ret curve;
  }
  
  void removeCurve(Curve curve) {
    curves.remove(curve);
    curve.start.outgoingCurves.remove(curve);
    curve.end.incomingCurves.remove(curve);
    _invalidateSignature();
  }
  
  // all anchor arities in descending order
  // (a sort of fingerprint of the mesh)
  int[] sortedArities() {
    int[] array = mapToIntArray(anchors(), a -> a.arity());
    ret sortIntArrayInPlaceDesc(array);
  }
  
  S sortedAritiesToString aka aritySignature aka signature() {
    try object cachedSignature;
    int[] arities = sortedArities();
    bool compact = all(arities, arity -> arity < 10);
    ret cachedSignature = compact
      ? join(asList(arities))
      : roundBracket(joinWithComma(asList(arities)));
  }
  
  toString {
    ret "Mesh type " + sortedAritiesToString();
  }
  
  // re-number anchors starting from 1 after anchors were removed
  void renumberAnchors {
    int i = 0;
    for (anchor : anchors())
      anchor.index = ++i;
  }

  public Rect bounds() {
    new BoundsFinder bf;
    for (p : keys(anchorMap)) bf.add(p);
    for (curve : curves)
      for (p : curve.path.pointIterator())
        bf.add(p);
    ret bf!;
  }

  public int getWidth() { ret bounds().w; }
  public int getHeight() { ret bounds().h; }

  public BufferedImage getBufferedImage() {
    var r = bounds();
    ret new G22VisualizeMeshes(widthAndHeight(r.x2()+2, r.y2()+2), ll(this))!;
  }
  
  void _invalidateSignature {
    cachedSignature = null;
  }
  
  bool containsAnchor(Anchor a) {
    ret a != null && anchorMap.get(a.pt) == a;
  }
  
  bool containsCurve(Curve c) {
    ret curves.contains(c);
  }
  
  L<Curve> curveList() { ret asList(curves); }
  
  // SOME OPERATIONS
  
  void moveAnchor(Anchor a, Pt p) {
    if (eq(a.pt(), p)) ret;
    assertNotNull(p);
    anchorMap.remove(a.pt);
    a.pt = p;
    anchorMap.put(p, a);
  }
  
  // coalesce a1 into a2, keeping a2's position intact
  void mergeAnchorInto(Anchor a1, Anchor a2) {
    mergeAnchors(a1, a2, a2.pt);
  }
  
  // merges a1 and a2 (and their connections) into a new anchor
  // at newPosition
  void mergeAnchors(Anchor a1, Anchor a2, Pt newPosition) {
    if (scaffoldingEnabled())
      printVars("mergeAnchors", mesh := this, +a1, +a2, +newPosition);
    assertNotSame(a1, a2);
    assertNotNull(a1);
    assertNotNull(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);
    }
    
    moveAnchor(a2, newPosition);
    removeAnchor(a1);
  }
}

Began life as a copy of #1035010