// 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);

  }

}