MODULE SMap;
(* 
  A map will be represented by an object with two fields: "f" and "c"
  where "f" is a face describing the map and "c" is a corner of the
  map whose left face is "f".  In fact, "f" is not any face of the
  map. To provide auxiliary information for point location, we will
  assume the existence of a reference point which will be defined as
  the North Pole (the point whose homogeneous coordinate is
  "[1,0,0,1]" and whose Plucker coefficients is
  "<0,0,1,0,0,0>"). Thus, a map is described by its face containing
  the reference point. In the particular case, when the reference
  point is on a border of the map, that is, when it is on an edge or
  is a vertex, we will store in the field "c", the corner representing
  that edge or that vertex and "f" is the left face of that
  corner. It's worth mentioning that if the reference point lies on a
  face (i.e, it's not on an edge neither on a vertex) the field
  "c" will be set to "NIL".

  In the procedures involving intersection between an edge "e" and map
  (or some borders of it), we firstly compute the points of
  intersection between the edge "e" and the borders and secondly, we
  process these points. So, besides the coordinates of the
  intersection points, we also need to keep track the edges of the map
  that generate those points. To do this, we define a type InterPoint
  consisting of a record with two fields "p" and "which", where "p" is
  the "coordinates" of intersection point and "which" is the corner
  representing the edge that generated it. Also, we use the field
  "next" to make a linked list of these points.
  
  Created in Sep. 16, 1997 by Marcus Vinicius A. Andrade
  Last edited in Sep. 22, 1997 by Marcus Vinicius A. Andrade
*)
  
FROM SMGeo IMPORT Point, Circle, Arc, Sign;
FROM SMTop IMPORT Face, Border, Corner; 
FROM SMCFeat IMPORT VFType, EFType;
FROM PSPlot IMPORT Color;

IMPORT SMCFeat, SMGeo, SMTop, SMBorder, SMPoint, SMCircle, SMDraw, Fmt, FileFmt, NGet, NPut, FGet, FPut, FileRd, FileWr, Lex, Scan, Rd, Wr, Text, Stdio, OldFmt;

CONST 
  (* ===== Constants for file format ===== *)
  SMVersion = "97-10-20";
  
  (* ===== Constant defining the kind of perturbation ==== *)
  CPerturb = +1;

REVEAL 
  (* ====== list of intersection points ====== *) 
  InterPoint = BRANDED REF RECORD 
    p       : Point;       (* coordinates of the intersection point  *)
    which   : Corner;      (* which corner generated that point      *)
    next    : InterPoint;  (* next intersection point                *)
  END;  
   
  ListOfInterPoints = BRANDED REF RECORD  
    n : CARDINAL;
    l : InterPoint;
  END;

  (* ========== Definition of Map ================ *)  
  T = PublicMap BRANDED OBJECT 
    ValidNumber : BOOLEAN:=TRUE; (* TRUE => map's numeration is valid          *)
    NV, NE      : CARDINAL;      (* number of Vertices and Edges               *)
  OVERRIDES                
    init := CreateMap;
    makeVertex := MakeVertex;
    delIsolatedVertex := DelIsolatedVertex;
    makeEdge := MakeEdge;
    delEdge := DelEdge;
    whereTo := WhereTo;
    whichEdge := WhichEdge;
    pointLocation := PointLocation;
    intersectEdgeWithElement := IntersectEdgeWithElement;
    numerate := NumerateMap;
    read := ReadMap;
    write := WriteMap;
    draw := DrawMap;
  END; 

VAR RefPoint : InterPoint;

(* ====================================================================== *)
(*   procedures to manipulate the geometry of vertices, edges and arcs    *)
(* ====================================================================== *)

PROCEDURE SetVertexGeometry(v: Vertex; p: Point) = 
  BEGIN
    v.org().setGeom(p)
  END SetVertexGeometry;

PROCEDURE GetVertexGeometry(v: Vertex) : Point = 
  BEGIN
    RETURN v.org().getGeom()
  END GetVertexGeometry;

PROCEDURE GetEdgeGeometry(e: Edge) : Circle = 
  BEGIN
    IF e.fwd() = 1 THEN 
      RETURN e.edg().getGeom()
    ELSE 
      RETURN SMGeo.InvRing(e.edg().getGeom())
    END
  END GetEdgeGeometry;

PROCEDURE GetArcGeometry(e: Edge) : Arc = 
  BEGIN
    WITH sarc = e.getGeoOfArc(e.cSym()) DO 
      IF e.fwd() = -1 THEN 
        RETURN SMGeo.InvArc(sarc)
      ELSE 
        RETURN sarc
      END
    END
  END GetArcGeometry;

PROCEDURE SetArcGeometry(e: Edge; sc: Circle; p: Point:=NIL; q: Point:=NIL) = 
  BEGIN
    IF p # NIL THEN 
      IF e.isRing() THEN  (* --- creates a vertex in that ring --- *)
        e.initVertex();
      END;
      SetVertexGeometry(e,p); 
    END;
    WITH edg = e.edg() DO 
      edg.setGeom(sc);          (* --- sets the geometry of "e" --- *) 
      e.setEdge(edg,+1);        (* --- sets the direction of "e" --- *)
      WITH es = e.cSym() DO 
        IF q # NIL THEN 
          IF SMGeo.AreSamePoints(p,q) THEN
            (* --- since "p = q" then "e.org" and "es.org" use a  
                   same vertex's feature record --- *) 
            es.setVertex(e.org())      
          ELSE 
            IF es.isRing() THEN  
              (* --- creates a vertex in that ring --- *)
              es.initVertex();
            ELSIF e.org() = es.org() THEN 
              (* --- "e" was a loop, i.e. "origin" and destination had a same 
                     feature's record, then creates a vertex for "e.cSym()" *) 
              es.initVertex();
            END;
            SetVertexGeometry(es,q);   
          END
        END;
        (* --- "e.edg" and "es.edg" use a same edge's feature record; 
                but "e" and "es" have opposite direction given by "d" --- *)  
        es.setEdge(edg,-1);   
      END
    END;
  END SetArcGeometry;

PROCEDURE CreateCornerAndFeatures(sc: Circle; p,q: Point) : Corner = 
  BEGIN
    IF p=NIL AND q=NIL THEN (* --- creates a ring --- *)
      WITH e=NEW(Corner).createRing() DO 
        e.initEdge();
        SetArcGeometry(e,sc);
        RETURN e
      END
    ELSIF sc=NIL AND p#NIL THEN (* --- creates an isolated vertex --- *)
      WITH v=NEW(Corner).createIsolatedVertex() DO 
        v.initVertex();
        SetVertexGeometry(v,p);
        RETURN v
      END
    ELSE (* --- creates an arc --- *)
      WITH e = NEW(Edge).createEdge() DO
        e.initEdge();
        e.initVertex();
        IF NOT SMGeo.AreSamePoints(p,q) THEN e.cSym().initVertex(); END;
        SetArcGeometry(e,sc,p,q);
        RETURN e
      END
    END
  END CreateCornerAndFeatures;

(* ================================================= *)
(*   Manipulation of the List of Intersection Points *)
(* ================================================= *)
PROCEDURE InitializeLIP() : ListOfInterPoints = 
  BEGIN
    WITH lip = NEW(ListOfInterPoints) DO
      lip^.n:=0;
      lip^.l:=NIL;
      RETURN lip
    END
  END InitializeLIP;

PROCEDURE InsNode(lip: ListOfInterPoints; p: Point; c: Corner) =
  BEGIN
    WITH node = NEW(InterPoint) DO
      node^.p := p;
      node^.which := c;
      node^.next := lip^.l;
      lip^.l:=node;
      lip^.n:=lip^.n+1
    END;
  END InsNode;

PROCEDURE MergeList(l1,l2: ListOfInterPoints) : ListOfInterPoints =
  VAR auxs,auxb : InterPoint;
      ml := NEW(ListOfInterPoints);
  BEGIN
    IF l2^.l = NIL THEN 
      RETURN l1
    ELSIF l1^.l = NIL THEN 
      RETURN l2
    ELSE
      IF l1^.n >= l2^.n THEN 
        auxs:=l2^.l;
        auxb:=l1^.l
      ELSE 
        auxs:=l1^.l;
        auxb:=l2^.l
      END;
      WHILE auxs^.next # NIL DO
        auxs:=auxs^.next
      END;
      auxs^.next:=auxb;
      ml^.l:=auxs;
      ml^.n:=l1^.n+l2^.n;
      RETURN ml
    END
  END MergeList;

(* ================================================= *)
(*  Manipulation of the Stack of Vertices and Edges  *)
(* ================================================= *)
TYPE 
  VStack = REF ARRAY OF VFType;
  EStack = REF ARRAY OF EFType;
  BStack = REF ARRAY OF Border;
  FStack = REF ARRAY OF Face;
  
CONST 
  StackSize=127;

PROCEDURE IsOutOfStackRange(stack: REFANY; i: CARDINAL) : BOOLEAN = 
  BEGIN
    TYPECASE stack OF 
    | VStack(vStack) => RETURN i > NUMBER(vStack^)-1;
    | EStack(eStack) => RETURN i > NUMBER(eStack^)-1;
    | BStack(bStack) => RETURN i > NUMBER(bStack^)-1;
    | FStack(fStack) => RETURN i > NUMBER(fStack^)-1;
    ELSE
    END
  END IsOutOfStackRange;

PROCEDURE DoubleStackSize(stack: REFANY) = 
  BEGIN
    TYPECASE stack OF 
    | VStack(vStack) => WITH
                          ss = NUMBER(vStack^),
                          ssn = 2*ss,
                          newstack = NEW(VStack,ssn)
                        DO
                          SUBARRAY(newstack^,0,ss) := vStack^;
                          vStack:=newstack
                        END;
    | EStack(eStack) => WITH
                          ss = NUMBER(eStack^),
                          ssn = 2*ss,
                          newstack = NEW(EStack,ssn)
                        DO
                          SUBARRAY(newstack^,0,ss) := eStack^;
                          eStack:=newstack
                        END;

    | BStack(bStack) => WITH
                          ss = NUMBER(bStack^),
                          ssn = 2*ss,
                          newstack = NEW(BStack,ssn)
                        DO
                          SUBARRAY(newstack^,0,ss) := bStack^;
                          bStack:=newstack
                        END;
    | FStack(fStack) => WITH
                          ss = NUMBER(fStack^),
                          ssn = 2*ss,
                          newstack = NEW(FStack,ssn)
                        DO
                          SUBARRAY(newstack^,0,ss) := fStack^;
                          fStack:=newstack
                        END;
    ELSE
    END;
  END DoubleStackSize;

(* ================================================= *)
(*          General Internal Procedures              *)
(* ================================================= *)
PROCEDURE NextPointOnEdge(ip: InterPoint; e: Edge; lip: ListOfInterPoints) : InterPoint = 
  (* ------------------------------------------------------------------ *)
  (* Given a list of points on a edge "e" and a point "p", also on that *)
  (* edge, returns the first point after "p" in that list considering   *)
  (* the orientation of "e"                                             *)
  (* ------------------------------------------------------------------ *)
  VAR sc           : Circle;
      fap,r,br,bf  : InterPoint;
  BEGIN
    sc:=GetEdgeGeometry(e);
    
    IF lip^.l = NIL THEN   (* if list is empty *)
      RETURN NIL
    ELSE
      fap:=lip^.l;         (* "fap" starts as the first point in the list *)
      br:=NIL;
      bf:=br;
      r:=fap^.next;
      
      (* --- checks if the first point in "lip" is equal to "ip" --- *)
      IF NOT SMGeo.AreSamePoints(ip^.p,fap^.p) THEN  
        WHILE r # NIL DO 
          WITH s = SMGeo.CircOrd3PointsOnCircle(ip^.p,r^.p,fap^.p,sc) DO
            IF s >= 0 THEN   (* "r" is between "p" and "fap" or on one of them *)
              bf:=br;
              fap:=r;
              IF s=0 AND SMGeo.AreSamePoints(ip^.p,r^.p) THEN  
                (* "r" is equal to the initial point then we can stop the search *)
                EXIT 
              END
            ELSIF SMGeo.AreSamePoints(ip^.p,fap^.p) THEN 
              EXIT 
            END
          END;
          br:=r;
          r:=r^.next;
        END
      END;
      (* ====== remove "fap" from the list "lip" ====== *)
      IF bf = NIL THEN 
        (* "fap" is the first point in the list *)
        lip^.l:=lip^.l^.next
      ELSE
        bf^.next:=fap^.next  
      END;
      fap^.next:=NIL;
      lip^.n:=lip^.n-1;
      RETURN fap
    END
  END NextPointOnEdge;

PROCEDURE SortPointsOnEdge(lip: ListOfInterPoints; e: Edge) : ListOfInterPoints = 
  VAR slip   : ListOfInterPoints;  (* sorted list *)
      ip,ult : InterPoint;
  BEGIN
    slip := InitializeLIP();
    (* ---------------------------------------------------------- *)
    (* Creates an InterPoint record for an initial point on edge; *)
    (* if "e" is a ring, it's taken the first point in "lip"      *)
    (* ---------------------------------------------------------- *)
    ip := NEW(InterPoint);
    IF e.isRing() AND lip^.l # NIL THEN  
      ip^.p := lip^.l^.p
    ELSE
      ip^.p := GetVertexGeometry(e)
    END;
    ip^.which := e;
    ip^.next:=NIL;
   
Wr.PutText(Stdio.stdout,"Em SortPointsOnEdge -- Fiz initial point \n");
Wr.Flush(Stdio.stdout);
   
    (* ====== Inserts the first point in the list "slip" ====== *)
    slip^.l := NextPointOnEdge(ip,e,lip);  
    slip^.n:=1;

Wr.PutText(Stdio.stdout,"Em SortPointsOnEdge -- Retornou de NextPointOnEdge ip = ");
SMPoint.PrintCpoint(Stdio.stdout,slip^.l^.p^);
Wr.PutText(Stdio.stdout,"\n");
Wr.Flush(Stdio.stdout);

    (* ====== Sorts the points in "lip" putting them in "slip" ====== *)
    ult := slip^.l;
    ip := lip^.l;
    WHILE ip # NIL DO 
      ip := NextPointOnEdge(ult,e,lip);
      IF ip # NIL THEN 
        ult^.next:=ip;
        slip^.n:=slip^.n+1;
        ult:=ip
      END
    END;
    RETURN slip
  END SortPointsOnEdge;

PROCEDURE GeneratePointOnBorder(b: Border) : InterPoint = 
  (* ------------------------------------------------------------- *)
  (* returns a point on the border "b" and the corner where it is  *)
  (* ------------------------------------------------------------- *)
  VAR ip: InterPoint;
  BEGIN
    ip:=NEW(InterPoint);
    WITH c = b.borderDesc() DO

Wr.PutText(Stdio.stdout,"Em GeneratePointOnBorder --- corner = "&Fmt.Int(c.getNum())&" IsRing = "&Fmt.Bool(c.isRing())&"\n");
Wr.Flush(Stdio.stdout);

      IF NOT c.isRing() THEN 
        ip^.p:=GetVertexGeometry(c)
      ELSE
        ip^.p:=SMGeo.GeneratePointOnCircle(GetEdgeGeometry(c))
      END;
      ip^.which:=c;
      ip^.next:=NIL;

(*
Wr.PutText(Stdio.stdout,"Em GeneratePointOnBorder --- p = ");
SMPoint.PrintCpoint(Stdio.stdout,ip^.p^);
IF NOT c.isIsolatedVertex() THEN 
Wr.PutText(Stdio.stdout," Side(p,border) = "&Fmt.Int(SMGeo.SidePointCircle(ip^.p,GetEdgeGeometry(c)))&"\n");
END;
Wr.Flush(Stdio.stdout);
*)

    END;
    RETURN ip
  END GeneratePointOnBorder;
  
PROCEDURE RelativePositionOfReferencePoint(m: T; b: Border) : Sign =
  (* ------------------------------------------------------------------ *)
  (* Given the border "b", returns +1 if the reference point is on the  *)
  (* left ("interior") side of the border, 0 if it is on the border and *)
  (* -1 if it is on the right ("exterior") side of the border           *)
  (* ------------------------------------------------------------------ *)

  VAR sc  : Circle;
      cp  : InterPoint;
      lip : ListOfInterPoints;
  BEGIN

Wr.PutText(Stdio.stdout,"Entrou em RelativePositionOfReferencePoint \n ");
Wr.Flush(Stdio.stdout);
  
    WITH 
      pb = GeneratePointOnBorder(b),
      sc = SMGeo.CircleByTwoPoints(pb^.p,RefPoint^.p),
      (* --- edge from RefPoint to pb --- *)
      e = CreateCornerAndFeatures(sc,RefPoint^.p,pb^.p)
    DO 
      lip:=m.intersectEdgeWithElement(e,FALSE,b);

Wr.PutText(Stdio.stdout,"Em RelativePositionOfReferencePoint -- Fez IntersectEdgeWithElement \n ");
Wr.Flush(Stdio.stdout);

      IF lip^.l # NIL THEN 

Wr.PutText(Stdio.stdout,"Em RelativePositionOfReferencePoint -- LIP NAO vazia \n ");
Wr.Flush(Stdio.stdout);

        cp:=NextPointOnEdge(RefPoint,e,lip);
        
Wr.PutText(Stdio.stdout,"Em RelativePositionOfReferencePoint -- cp = ");
SMPoint.PrintCpoint(Stdio.stdout,cp^.p^);
Wr.PutText(Stdio.stdout,"  edge = ");
SMCircle.Print(Stdio.stdout,GetEdgeGeometry(cp^.which)^);
Wr.PutText(Stdio.stdout,"\n");
Wr.Flush(Stdio.stdout);
      
      ELSE
      (* --------------------------------------------------------- *)
      (* since the edge connecting RefPoint to "pb" didn't meet    *)
      (* then the relative position of RefPoint is given by the    *)
      (* side of RefPoint relative to the corner of "pb"           *)
      (* --------------------------------------------------------- *)
        cp := pb
      END;
          
      IF SMGeo.AreSamePoints(cp^.p,RefPoint^.p) THEN 
        (* ------------------------------------------------------ *)
        (* the border "b" passes through RefPoint; i.e., RefPoint *)
        (* is on an edge or on a vertex of the border             *)
        (* ------------------------------------------------------ *)
        RefPoint^.which:=cp^.which;
        RETURN 0
      ELSE
        RETURN SMGeo.SidePointCircle(RefPoint^.p,GetEdgeGeometry(cp^.which))
      END;
    END
  END RelativePositionOfReferencePoint; 
  
PROCEDURE LocatePointRelativeToBorder(m: T; p: Point; b: Border) : Sign =
  (* ------------------------------------------------------------------ *) 
  (* Returns +1 if the point "p" is on the left side of the border "b"; *)
  (* that is, if "p" is "inside" the border "b". If "p" is on the       *)
  (* border "b" then returns 0 and if "p" is on the right side of "b"   *)
  (* then returns -1.                                                   *)
  (* ------------------------------------------------------------------ *) 
  VAR sc    : Circle;
      ip,cp : InterPoint;
      lip   : ListOfInterPoints;
  BEGIN
    IF SMGeo.AreSamePoints(p,RefPoint^.p) THEN 
      RETURN RelativePositionOfReferencePoint(m,b)
    ELSE 
      WITH 
        sc = SMGeo.CircleByTwoPoints(p,RefPoint^.p),
        e = CreateCornerAndFeatures(sc,p,RefPoint^.p)
      DO 
        lip:=m.intersectEdgeWithElement(e,FALSE,b);

Wr.PutText(Stdio.stdout,"Em LocatePointRelativeToBorder -- Voltou de Intersect \n ");
Wr.Flush(Stdio.stdout);

        IF lip^.l = NIL THEN 
          (* -----------------------------------------------------------*)
          (* if the edge connecting "p" to RefPoint doesn't intersect   *)
          (* the border "b" or (p=RefPoint) then "p" and RefPoint have  *)
          (* a same position realtive to "b"                            *)
          (* ---------------------------------------------------------- *)

Wr.PutText(Stdio.stdout,"Em LocatePointRelativeToBorder -- LIP Vazia \n ");
Wr.Flush(Stdio.stdout);

          RETURN RelativePositionOfReferencePoint(m,b)
        ELSE
          (* -------------------------------------------------------- *)
          (* creates a InterPoint record for the point "p"            *)
          (* -------------------------------------------------------- *)
          ip:=NEW(InterPoint);
          ip^.p:=p;
          ip^.which:=NIL;
          ip^.next:=NIL;
          cp:=NextPointOnEdge(ip,e,lip);
          RETURN SMGeo.SidePointCircle(p,GetEdgeGeometry(cp^.which))
        END
      END
    END
  END LocatePointRelativeToBorder;

PROCEDURE MergeBorders(m: T; f1,f2 : Face) : Face =
   (* ---------------------------------------------------------- *)
   (* Returns a "new" face with all the borders of "f1" and "f2" *)
   (* ---------------------------------------------------------- *)
   VAR sf,nf  : Face;  
      sb     : SMBorder.T;
      b      : Border;
  BEGIN
    (* ------------------------------------------------------------- *)
    (* choose the "smallest" face, i.e. the face with fewest borders *) 
    (* ------------------------------------------------------------- *)
    IF f1.size() <= f2.size() THEN 
      sf := f1;
      nf := f2;
    ELSE
      sf := f2;
      nf := f1;
    END;
    (* ------------------------------------------------------------- *)
    (* transfer the borders of the "smallest" face to the "new face  *)
    (* ------------------------------------------------------------- *)
    WITH it = sf.bordersOf().iterate() DO
      WHILE it.next(sb) DO 
        b:=NARROW(sb,Border);
        nf.transferBorder(b)
      END;
    END;
    (* ------------------------------------------------------------- *)
    (* if the "smallest" face is the face containing the reference   *)
    (* point then updates the record describing the map              *)
    (* ------------------------------------------------------------- *)
    IF m.refFace() = sf THEN  
      m.setRefFace(nf)
    END;
    RETURN nf
  END MergeBorders;

PROCEDURE DistributeBorders(m: T; e: Edge; f,fc,fd : Face) = 
  (* 
    Given the set of borders "f", distributes that borders among the
    faces "fc" and "fd"; this distribution is based on the geometry of
    the edge "e" and, for each border of "f", we decide whether it is
    either on the left side of "e" or on the right side. It's a
    partition of "f". Besides, if the "f" is the face representing the
    map "m" (that is, containing the reference point) then determines
    which of faces "fc" or "fd" will be the new map's representing
    face.
    
    Since at the begining, each face "fc" and "fd" has just one border
    and the borders of "f" don't intersect these initial borders then
    we need only to decide if each border of "f" is either "inside"
    the border of "fc" or "inside" the border of "fd" *)

  VAR b  : Border;       (* "bc" will store the initial border of the face "fc" *)
      sb : SMBorder.T;    (* the ancestor of border; to do a set of borders *)
      sarc : Arc;
      s : Sign;
  BEGIN
    (* ----------------------------------------------------- *)
    (* Distributes the borders of "f" between "fc" and "fd"  *)
    (* ----------------------------------------------------- *)
    
    sarc:=GetArcGeometry(e);
    
    WITH itf = f.bordersOf().iterate() DO
      WHILE itf.next(sb) DO 
        b:=NARROW(sb,Border);
        WITH ip = GeneratePointOnBorder(b) DO 
          EVAL SMGeo.IsPointInArc(ip^.p,sarc,s);
       
Wr.PutText(Stdio.stdout,"\n +++++ Em DistributeBorders -- Depois de LocatePointRelativeToBorder s = "&Fmt.Int(s)&"\n ");
Wr.Flush(Stdio.stdout);

          (* ---------------------------------------------------------- *)
          (* if "s>=0" then point "pb" (that is, the border "b") is     *)
          (* on the left face, i.e., "bc" will be a border of "fc";     *)
          (* else ("s<0"), then "bc" will be a border of "fd"           *)
          (* ---------------------------------------------------------- *)
          IF s >= 0 THEN 
            fc.transferBorder(b)
          ELSE
            fd.transferBorder(b)
          END
        END;  
      END;
    END;
  
    (* ------------------------------------------------------------ *)
    (* If the face has been distributed is the face containing the  *)
    (* reference point, then determine which face will receive it   *)
    (* ------------------------------------------------------------ *)
    IF f = m.refFace() THEN 

Wr.PutText(Stdio.stdout,"Em DistributeBorders -- Setendo RefFace \n ");
Wr.Flush(Stdio.stdout);
    
      EVAL SMGeo.IsPointInArc(RefPoint^.p,sarc,s);
      IF s >= 0 THEN 
        m.setRefFace(fc);
        IF s=0 THEN 
          m.setRefCorner(e)
        END 
      ELSE 
        m.setRefFace(fd)
      END
    END;
  END DistributeBorders;

PROCEDURE BreakEdge(m: T; p: Point; e: Edge) : Vertex =
  (* breaks the edge "e" inserting it the point "p"; 
     returns the corner representing the vertex in the same 
     border as "e"; that is, returns "e.bNext"  *)
  VAR v : Vertex;
      q1,q2: Point;
  BEGIN

Wr.PutText(Stdio.stdout,"Em BreakEdge -- Ponto caiu em cima da aresta "&OldFmt.Ref(e)&"\n");
Wr.Flush(Stdio.stdout);

    IF e.isRing() THEN 
      (* --------------------------------------------- *)
      (* if "self" is a ring, just transforms it into  *)
      (* a loop setting its feature record             *)
      (* --------------------------------------------- *)
      e.initVertex();
      SetVertexGeometry(e,p);
      e.cSym().setVertex(e.org());
    ELSE 
      q1:=GetVertexGeometry(e);
      (* --- "q1" will be the origin of the "new" edge --- *)
      IF SMGeo.AreSamePoints(p,q1) THEN 
        RETURN e
      END;
 
      q2:=GetVertexGeometry(e.cSym());
      (* --- "q2" will be the destination of the "new" edge --- *)
      IF SMGeo.AreSamePoints(p,q2) THEN 
        RETURN e.cSym()
      END;
 
      WITH 
        sc = GetEdgeGeometry(e),
        esOrg = e.cSym().org(),
        e2 = CreateCornerAndFeatures(sc,p,p),
        e2Org = e2.org()
      DO

Wr.PutText(Stdio.stdout,"Em BreakEdge -- antes de InsAfter e = "&OldFmt.Ref(e)&"  es = "&OldFmt.Ref(e.cSym())&"  eon = "&OldFmt.Ref(e.oNext())&"\n");
Wr.Flush(Stdio.stdout);

        e.insAfter(e2);

Wr.PutText(Stdio.stdout,"Em BreakEdge -- depois de InsAfter e = "&OldFmt.Ref(e)&"  es = "&OldFmt.Ref(e.cSym())&"  eon = "&OldFmt.Ref(e.oNext())&"\n");
Wr.Flush(Stdio.stdout);

        (* --- sets the vertices features of the "new" edges --- *)
        e.cSym().setVertex(e2Org);
        e2.cSym().setVertex(esOrg);
      END
    END;
    m.ValidNumber:=FALSE;
    RETURN e.bNext()
  END BreakEdge;

PROCEDURE MakeRing(m: T; e: Edge; sc: Circle; f: Face) =
  BEGIN
  
Wr.PutText(Stdio.stdout,"Em MakeRing -- \n ");
Wr.Flush(Stdio.stdout);
  
    WITH
      b = e.borderOf(),
      fc = b.faceOf(),
      fcs = e.cSym().faceOf()
    DO
    
Wr.PutText(Stdio.stdout,"Em MakeRing -- Voltou de PointLocation \n ");
Wr.Flush(Stdio.stdout);

      DistributeBorders(m,e,f,fc,fcs);
      
(*      (* --- if "f" (the face to be distributed) is the reference face 
             then set the "new" map's reference elements --- *)
      IF f = m.refFace() THEN 
        WITH s = RelativePositionOfReferencePoint(m,b) DO 
          IF s >= 0 THEN 
            m.setRefFace(fc);
            IF s = 0 THEN m.setRefCorner(e) END
          ELSE 
            m.setRefFace(fcs)
          END;
        END
      END;
*)      
      
    END;
    m.ValidNumber:=FALSE;
  END MakeRing;

PROCEDURE DelRing(m: T; e: Edge) : Face RAISES {ValidationError} = 
  BEGIN
    IF NOT e.isRing() THEN 
      RAISE ValidationError("In DelRing: the corner MUST be a ring")
    ELSE
      WITH 
        be = e.borderOf(),
        fe = be.faceOf(),
        es = e.cSym(),
        bes = es.borderOf(),
        fes = bes.faceOf()
      DO
        be.removeCorner(e);
        bes.removeCorner(es);
        m.ValidNumber:=FALSE;
        RETURN MergeBorders(m,fe,fes)
      END;
    END
  END DelRing;

PROCEDURE Connect(m: T; v1,v2: Vertex; c: Circle) : Edge = 
  VAR sp : Sign;
      f  : Face;
  BEGIN

m.write("MapBuilt.Out","");
WITH op=Lex.Int(Stdio.stdin) DO END;

Wr.PutText(Stdio.stdout,"Em Connect: Vai conectar --> v1 = ");
SMPoint.PrintCpoint(Stdio.stdout,GetVertexGeometry(v1)^);
Wr.PutText(Stdio.stdout,"  c1 = ");
SMCircle.Print(Stdio.stdout,GetEdgeGeometry(v1)^);
Wr.PutText(Stdio.stdout,"  v2 = ");
SMPoint.PrintCpoint(Stdio.stdout,GetVertexGeometry(v2)^);
Wr.PutText(Stdio.stdout,"  c2 = ");
SMCircle.Print(Stdio.stdout,GetEdgeGeometry(v2)^);
Wr.Flush(Stdio.stdout);

    WITH
      e = CreateCornerAndFeatures(c,GetVertexGeometry(v1),GetVertexGeometry(v2)), 
      es = e.cSym(),
      b = e.borderOf()
    DO
      f := v1.faceOf();
      f.transferBorder(b);
      e.setVertex(v1.org());
      es.setVertex(v2.org());


Wr.PutText(Stdio.stdout,"Em Connect: Na entrada f1 = f2 "&Fmt.Bool(v1.faceOf() = v2.faceOf())&"\n");

Wr.PutText(Stdio.stdout,"Em Connect: Antes DO primeiro splice  --> Face de Referencia = "&Fmt.Int(m.refFace().getNum())&"   Addr = "&OldFmt.Ref(m.refFace())&"\n");

Wr.PutText(Stdio.stdout,"Em Connect: Antes DO primeiro splice  --> b1 = "&Fmt.Int(v1.borderOf().getNum())&" f = "&Fmt.Int(f.getNum())&"  b2 = "&Fmt.Int(v2.borderOf().getNum())&" f Addr = "&OldFmt.Ref(f)&"\n");
Wr.Flush(Stdio.stdout);

      v1.splice(e); 
      
      WITH 
        nfe = e.faceOf(),
        nf1 = v1.faceOf()
      DO 
        IF nfe = nf1 THEN 
          nfe.mergeFaces(f);   
          IF m.refFace() = f THEN 
            m.setRefFace(nfe)
          END;
        ELSE 
          DistributeBorders(m,e,f,nf1,nfe)
        END;
      END;

m.ValidNumber:=FALSE;
m.write("MapBuilt.Out","");
Wr.PutText(Stdio.stdout,"Em Connect: Depois DO primeiro splice \n");
Wr.Flush(Stdio.stdout);
WITH op=Lex.Int(Stdio.stdin) DO END;

Wr.PutText(Stdio.stdout,"Em Connect: Depois DO primeiro splice  --> Face de Referencia = "&Fmt.Int(m.refFace().getNum())&"   Addr = "&OldFmt.Ref(m.refFace())&"\n");

Wr.PutText(Stdio.stdout,"Em Connect: Depois DO primeiro splice  --> b = "&Fmt.Int(b.getNum())&" f = "&Fmt.Int(f.getNum())&"  f Addr = "&OldFmt.Ref(f)&"\n");
Wr.Flush(Stdio.stdout);
      
      f := v2.faceOf();
      v2.splice(es);

      WITH 
        nf2 = v2.faceOf(),
        nfes = es.faceOf()
      DO 

Wr.PutText(Stdio.stdout,"Em Connect: Depois DO segundo splice (antes de setar) face de Referencia = "&OldFmt.Ref(m.refFace())&" f = "&OldFmt.Ref(f)&" nf2 = "&OldFmt.Ref(nf2)&" nfes = "&OldFmt.Ref(nfes)&"\n");

        IF nfes=nf2 THEN 
          nfes.mergeFaces(f);
          IF m.refFace() = f THEN 
            m.setRefFace(nfes)
          END 
        ELSE 
          DistributeBorders(m,es,f,nf2,nfes)
        END;
      END;

m.ValidNumber:=FALSE;
m.write("MapBuilt.Out","");
Wr.PutText(Stdio.stdout,"Em Connect: Depois DO segundo splice \n");
Wr.Flush(Stdio.stdout);
WITH op=Lex.Int(Stdio.stdin) DO END;
      
Wr.PutText(Stdio.stdout,"Em Connect: Depois DO segundo splice  --> Face de Referencia = "&Fmt.Int(m.refFace().getNum())&"   Addr = "&OldFmt.Ref(m.refFace())&"\n");

      RETURN e
    END
  END Connect;

(* ================================================= *)
(*          Implementation of the methods            *)     
(* ================================================= *)

PROCEDURE CreateMap(self: T): T =
  BEGIN
    EVAL NARROW(self, SMTop.Map).init();
    self.ValidNumber:= TRUE;
    self.NV:=0;
    self.NE:=0;
    RETURN self
  END CreateMap;

PROCEDURE MakeVertex(self: T; p: Point) : Vertex = 
  VAR v : Vertex;
  BEGIN

Wr.PutText(Stdio.stdout,"Entrou em MakeVertex p = ");
SMPoint.PrintCpoint(Stdio.stdout,p^);
Wr.PutText(Stdio.stdout,"\n");
Wr.Flush(Stdio.stdout);

    WITH elem = self.pointLocation(p) DO 
      TYPECASE elem OF 
      | Face(f) => BEGIN
                     (* --- creates a new isolated vertex in a dummy face --- *)
                     v := CreateCornerAndFeatures(NIL,p,NIL);

Wr.PutText(Stdio.stdout,"\nEm MakeVertex -- criei IsolatedVertex --- f.size "&Fmt.Int(f.size())&"\n");
Wr.Flush(Stdio.stdout);
                     
                     (* --- transfers the vertex from its dummy face to "f" --- *)
                     f.transferBorder(v.borderOf());

Wr.PutText(Stdio.stdout,"Em MakeVertex -- transferi borda \n ");
Wr.Flush(Stdio.stdout);
                 
                   END   
      | Edge(e) => v:=BreakEdge(self,p,e);
      
      ELSE
      END;
      self.ValidNumber := FALSE; 
    END;
    (* --- if the new vertex lies on the reference point AND 
           there isn't any reference corner yet; set it   --- *) 
    IF self.refCorner() = NIL AND SMGeo.AreSamePoints(p,RefPoint^.p) THEN 
      self.setRefCorner(v)
    END;
    RETURN v
  END MakeVertex;

PROCEDURE DelIsolatedVertex(self: T; v: Vertex) RAISES {ValidationError} =
  BEGIN
    IF NOT v.isIsolatedVertex() THEN 
      RAISE ValidationError("In DelIsolatedVertex: the corner MUST be an isolated vertex")
    ELSE
      (* --- If "v" lies on the reference point, sets the field "c" to NIL --- *)
      IF self.refCorner() # NIL AND 
            SMGeo.AreSamePoints(RefPoint^.p,GetVertexGeometry(v)) THEN 
        self.setRefCorner(NIL)
      ELSE 
        v.borderOf().removeCorner(v)
      END;
    END;
    self.ValidNumber:=FALSE;
  END DelIsolatedVertex;

PROCEDURE MakeEdge(self: T; c: Circle; p: Point:=NIL; q: Point:=NIL) : Edge = 
  VAR ip,ip1,ip2   : InterPoint; 
      lip,slip     : ListOfInterPoints;
      v1,v2        : Vertex;
      e,en         : Edge;
      f1           : Face;               (* origin's face *)
      close        : BOOLEAN := FALSE;
      elem         : REFANY; 
      cr           : Circle;
      pp           :=NEW(Point);
  BEGIN

    e := CreateCornerAndFeatures(c,p,q);

Wr.PutText(Stdio.stdout,"Em MakeEdge -- Voltou de CreateEdgeAndFeatures \n ");
Wr.Flush(Stdio.stdout);
    
    IF p#NIL THEN     (* --- edge to be created is not a ring --- *)
      v1:=self.makeVertex(p);
      IF q#NIL AND NOT SMGeo.AreSamePoints(p,q) THEN 
        EVAL self.makeVertex(q)
      END;
      IF v1.isIsolatedVertex() THEN 
        elem:=v1.faceOf()
      ELSE 
        elem := self.whereTo(v1,c,en)
      END
    ELSE 
      elem := self.pointLocation(SMGeo.GeneratePointOnCircle(c))
    END;
    TYPECASE elem OF 
    | Edge(e) => f1:=e.faceOf(); 
    | Face(f) => f1:=f
    ELSE 
    END;
    
    lip := self.intersectEdgeWithElement(e,TRUE,self,f1);
    
Wr.PutText(Stdio.stdout,"Em MakeEdge -- Fez IntersectEdgeWithElement \n ");
Wr.Flush(Stdio.stdout);

    IF (lip^.l = NIL) THEN 
      IF (p=NIL) AND (q=NIL) THEN  (* --- creates a ring --- *)
        MakeRing(self,e,c,f1)
      END;
    ELSE
      slip := SortPointsOnEdge(lip,e);

      (* --- creates the vertices corresponding to the intersection points --- *)
      ip1 := slip^.l;
      WHILE ip1 # NIL DO 
        WITH v = BreakEdge(self,ip1^.p,ip1^.which) DO 
          ip1^.which:=v
        END;
        ip1:=ip1^.next
      END;

self.ValidNumber:=FALSE;
self.write("MapBuilt.Out","");
Wr.PutText(Stdio.stdout,"Em MakeEdge: Depois dos BreakEdges \n");
Wr.Flush(Stdio.stdout);
WITH op=Lex.Int(Stdio.stdin) DO END;
      
      
      (* --- connects the vertices created above --- *)
      ip1:=slip^.l;
      ip2 := ip1^.next;
      cr:=SMGeo.InvRing(c);
      IF ip2 = NIL THEN  
        (* --- makes a loop --- *)
        WITH v = ip1^.which DO 
          en := Connect(self,v,v.cSym(),c);
        END
      ELSE 
        WHILE ip2 # NIL DO 

v1:=ip1^.which; v2:=ip2^.which;
Wr.PutText(Stdio.stdout,"Em MakeEdge -- Antes WhereTo --- v1 = "&OldFmt.Ref(v1)&" v1on = "&OldFmt.Ref(v1.oNext())&"  v1s = "&OldFmt.Ref(v1.cSym())&"\n");
Wr.PutText(Stdio.stdout,"Em MakeEdge -- Antes de WhereTo --- v2 = "&OldFmt.Ref(v2)&" v2on = "&OldFmt.Ref(v2.oNext())&"  v2s = "&OldFmt.Ref(v2.cSym())&"\n");
Wr.Flush(Stdio.stdout);

          
          EVAL self.whereTo(ip1^.which,c,v1);
          EVAL self.whereTo(ip2^.which,cr,v2);
        
Wr.PutText(Stdio.stdout,"Em MakeEdge -- Depois de WhereTo --- v1 = "&OldFmt.Ref(v1)&" v1on = "&OldFmt.Ref(v1.oNext())&"  v1s = "&OldFmt.Ref(v1.cSym())&"\n");
Wr.PutText(Stdio.stdout,"Em MakeEdge -- Depois de WhereTo --- v2 = "&OldFmt.Ref(v2)&" v2on = "&OldFmt.Ref(v2.oNext())&"  v2s = "&OldFmt.Ref(v2.cSym())&"\n");
Wr.Flush(Stdio.stdout);
          
          en:=Connect(self,v1,v2,c);

          ip1:=ip2;
          ip2:=ip2^.next;
        END;

        IF e.isRing() THEN
          EVAL self.whereTo(ip1^.which,c,v1);
          EVAL self.whereTo(slip^.l^.which,cr,v2);

Wr.PutText(Stdio.stdout,"Em MakeEdge -- FECHANDO \n");
Wr.PutText(Stdio.stdout,"Em MakeEdge -- v1 = "&OldFmt.Ref(v1)&" v1on = "&OldFmt.Ref(v1.oNext())&"  v1s = "&OldFmt.Ref(v1.cSym())&"\n");
Wr.PutText(Stdio.stdout,"Em MakeEdge -- v2 = "&OldFmt.Ref(v2)&" v2on = "&OldFmt.Ref(v2.oNext())&"  v2s = "&OldFmt.Ref(v2.cSym())&"\n");
Wr.Flush(Stdio.stdout);

          en:=Connect(self,v1,v2,c);  
        END  
      END;
    END;
    self.ValidNumber:=FALSE;
    RETURN en;
  END MakeEdge;

PROCEDURE DelEdge(self: T; e: Edge) = 
  BEGIN
    
  END DelEdge;

PROCEDURE PointLocation(self: T; p: Point) : REFANY =
  VAR sc    : Circle;
      ip,cp : InterPoint;
      lip   : ListOfInterPoints;
  BEGIN

Wr.PutText(Stdio.stdout,"Em PointLocation -- p = ");
SMPoint.PrintSpoint(Stdio.stdout,SMPoint.CToS(p^));
Wr.PutText(Stdio.stdout,"\n");
Wr.Flush(Stdio.stdout);

    IF SMGeo.AreSamePoints(p,RefPoint^.p)  THEN 

Wr.PutText(Stdio.stdout,"\nEm PointLocation -- Igual ao RefPoint \n ");
Wr.Flush(Stdio.stdout);

      IF self.refCorner() # NIL THEN (* --- that vertex already exists --- *)

Wr.PutText(Stdio.stdout,"Em PointLocation -- RefCorner # NIL \n ");
Wr.Flush(Stdio.stdout);

        RETURN self.refCorner()
      ELSE 
        RETURN self.refFace()
      END
    END;
      
Wr.PutText(Stdio.stdout,"Em PointLocation -- p = ");
SMPoint.PrintCpoint(Stdio.stdout,p^);
Wr.PutText(Stdio.stdout," e RefPoint = ");
SMPoint.PrintCpoint(Stdio.stdout,RefPoint.p^);
Wr.PutText(Stdio.stdout,"\n");
Wr.Flush(Stdio.stdout);

    sc:= SMGeo.CircleByTwoPoints(p,RefPoint^.p);

Wr.PutText(Stdio.stdout," ==> Circulo = ");
SMCircle.Print(Stdio.stdout,sc^);
Wr.PutText(Stdio.stdout,"\n");
Wr.Flush(Stdio.stdout);
    
    WITH 
      e = CreateCornerAndFeatures(sc,p,RefPoint^.p),
      es = e.cSym()
    DO

Wr.PutText(Stdio.stdout,"Em PointLocation -- Criou Aresta \n ");
Wr.Flush(Stdio.stdout);
      
      lip:=self.intersectEdgeWithElement(e,FALSE,self,self.refFace());

Wr.PutText(Stdio.stdout,"Em PointLocation -- Voltou de IntersectEdgeWithElement -- LIP.size = "&Fmt.Int(lip^.n)&"\n");
Wr.Flush(Stdio.stdout);

      IF lip^.l = NIL THEN 
        (* -----------------------------------------------------------*)
        (* if the edge connecting "p" to RefPoint doesn't intersect   *)
        (* the border "b" then "p" and RefPoint are on a same face.   *)
        (* ---------------------------------------------------------- *)

Wr.PutText(Stdio.stdout,"Em PointLocation -- LIP vazia \n ");
Wr.Flush(Stdio.stdout);

        RETURN self.refFace();
      ELSE
        (* -------------------------------------------------------- *)
        (* creates a InterPoint record for the point "p"            *)
        (* -------------------------------------------------------- *)
        ip:=NEW(InterPoint);
        ip^.p:=p;
        ip^.which:=NIL;
        ip^.next:=NIL;

Wr.PutText(Stdio.stdout,"Em PointLocation -- Criou ip \n ");
Wr.Flush(Stdio.stdout);
        
        cp:=NextPointOnEdge(ip,e,lip);

Wr.PutText(Stdio.stdout,"Em PointLocation -- Fez NextPointOnEdge: ");
Wr.PutText(Stdio.stdout," IsIsolatedVertex = "&Fmt.Bool(cp^.which.isIsolatedVertex())&" cp.p = ");
SMPoint.PrintCpoint(Stdio.stdout,cp^.p^);
Wr.Flush(Stdio.stdout);

        WITH crn = cp^.which DO 
          IF crn.isIsolatedVertex() THEN
            IF SMGeo.AreSamePoints(GetVertexGeometry(crn),p) THEN 
              RETURN crn
            ELSE
              RETURN crn.faceOf()
            END
          ELSE 
            WITH 
              circ = GetEdgeGeometry(crn),
              s = SMGeo.SidePointCircle(p,circ)
            DO
            
Wr.PutText(Stdio.stdout,"Em PointLocation -- Positicao de p em relacao a crn = "&Fmt.Int(s)&"\n");
Wr.Flush(Stdio.stdout);
            
              IF s = 0 THEN   (* "p" is either on a vertex or on an edge *)
                RETURN crn
              ELSIF s=1 THEN  (* "p" is on the left face of the edge *)
                RETURN crn.faceOf()
              ELSE            (* "p" is on the right face of the edge *)
                RETURN crn.cSym().faceOf()
              END
            END
          END
        END
      END
    END
  END PointLocation;

PROCEDURE WhereTo(self: T; v: Vertex; c: Circle; VAR e: Edge): REFANY = 
  VAR a1,a2,aaux : Arc;
      v1,v2      : Vertex;
      s : Sign;
      q : Point;
  BEGIN
    IF v.isIsolatedVertex() THEN 
      e:=v;
      RETURN v.faceOf()
    ELSE 
      WITH 
        p = GetVertexGeometry(v),
        sarc = SMGeo.SetGeoOfArc(p,p,c)  
      DO 
        v1:=v;
        v2:=v.oNext();
        LOOP 
          a1 := GetArcGeometry(v1);
          a2 := GetArcGeometry(v2);
          s := SMGeo.CircOrdOf3ArcsAroundVertex(a1,sarc,a2,p);
          IF s = 1 THEN 
            (* --- in counterclockwise direction, "sarc" is after "a1" 
                   and before "a2" --- *)
            e:=v1;
            RETURN v1.faceOf()
          ELSIF s = 0 THEN 
            (* --- the supporting circles of two arcs are coincident --- *)
            q:=NEW(Point);
            EVAL SMCircle.Intersection(a1^.c^,sarc^.c^,FALSE,q^);
            IF SMPoint.IsCpointNull(q^) THEN 
              e:=v1;
              RETURN v1
            ELSE 
              EVAL SMCircle.Intersection(a2^.c^,sarc^.c^,FALSE,q^);
              IF SMPoint.IsCpointNull(q^) THEN 
                e:=v2;
                RETURN v2
              END
            END;
          END;        
          v1:=v2;
          v2:=v2.oNext()
        END
      END
    END 
  END WhereTo;

PROCEDURE WhichEdge(self: T; v: Vertex; c: Circle): Edge =
  VAR ip  := NEW(InterPoint);
      lip : ListOfInterPoints;
      f   : Face;   (* starting face where the searching will start *)
  BEGIN
    WITH
      p = GetVertexGeometry(v),
      e = CreateCornerAndFeatures(c,p,p)
    DO
      ip^.p:=p;
      ip^.which:=v;
      ip^.next:=NIL;
      WITH elem = self.pointLocation(p) DO 
        TYPECASE elem OF 
        | Edge(e) => f:=e.faceOf(); 
        | Face(faux) => f:=faux
        ELSE 
        END        
      END;
      lip := self.intersectEdgeWithElement(e,FALSE,self,f);
      IF lip^.l = NIL THEN  (* === Didn't meet any edge === *)
        RETURN v           
      ELSE
        ip := NextPointOnEdge(ip,e,lip);
        WHILE lip^.l # NIL AND ip^.which.isIsolatedVertex() DO 
          ip := NextPointOnEdge(ip,e,lip);
        END;
        IF lip^.l = NIL THEN (* --- didn't meet an edge --- *) 
          RETURN ip^.which
        ELSE 
          RETURN NIL 
        END
      END
    END
  END WhichEdge;

PROCEDURE IntersectEdgeWithElement(self: T; e: Edge; tangency: BOOLEAN; 
                       elem: REFANY; startingface:Face:=NIL) : ListOfInterPoints =
  (* Computes the points of intersection between the edge "e" and 
     an element of the map (i.e the whole map, a face or a border); 
     the parameter "tangency" specifies if we will consider the intersection 
     between two tangent arcs. Also, if "elem" is the whole map then 
     "startingface" speficies a face where to start the searching *)

  VAR lip : ListOfInterPoints;
      earc : Arc;
      
  PROCEDURE IntersectTwoCorners(c: Corner) = 
    VAR p : Point;
        carc : Arc;
        sp : Sign;
    BEGIN
    
Wr.PutText(Stdio.stdout,"Entrou IntersectTwoCorners \n");
Wr.Flush(Stdio.stdout);

      IF c.isIsolatedVertex() THEN 
        WITH 
          v = c.org(),
          vn = v.getNum()
        DO 

Wr.PutText(Stdio.stdout," Em IntersectTwoCorners --> vertex = "&Fmt.Int(vn));
Wr.Flush(Stdio.stdout);

          WITH p = GetVertexGeometry(c) DO 
            IF SMGeo.IsPointInArc(p,earc,sp) THEN 

Wr.PutText(Stdio.stdout," ==> ");
SMPoint.PrintCpoint(Stdio.stdout,p^);
Wr.PutText(Stdio.stdout," sp = "&Fmt.Int(sp)&"\n");
                
              InsNode(lip,p,c)
            END;
          END
        END
      ELSE 
        WITH 
          e = c.edg(),
          en = e.getNum()
        DO 

Wr.PutText(Stdio.stdout," Em IntersectTwoCorners --> edge = "&Fmt.Int(en)&" fwd = "&Fmt.Int(c.fwd())&"\n ");
Wr.Flush(Stdio.stdout);

          WITH
            carc = GetArcGeometry(c),
            ok = SMGeo.IntersectionOfTwoArcs(carc,earc,CPerturb,tangency,p)
          DO

Wr.PutText(Stdio.stdout," Em IntersectTwoCorners --> carc = ");
SMGeo.PrintArc(Stdio.stdout,carc);
IF ok THEN 
Wr.PutText(Stdio.stdout," p = ");
SMPoint.PrintCpoint(Stdio.stdout,p^);
END;
Wr.PutText(Stdio.stdout,"\n");
Wr.Flush(Stdio.stdout);

            IF ok THEN 
              InsNode(lip,p,c)
            END
          END
        END
      END
    END IntersectTwoCorners;
    
  PROCEDURE IntersectEdgeWithMap() = 
    VAR fStack : FStack;
        ip: InterPoint;
    BEGIN
      IF NOT self.ValidNumber THEN 
        self.numerate()
      END;
      WITH cnt=self.getTCounter() DO 
        fStack:=NEW(FStack,cnt.NF+1);
      END;

      (* --- computes the intersection between "e" and the starting face "f" --- *)
      startingface.walkOn(IntersectTwoCorners,FALSE); 
      fStack[startingface.getNum()]:=startingface;

      ip:=lip^.l;
      WHILE ip # NIL DO 
        WITH
          es = ip^.which.cSym(),
          f=es.faceOf(),
          fn=f.getNum()
        DO 
          IF fStack[fn] = NIL THEN   (* face was not visited yet *)
            f.walkOn(IntersectTwoCorners,FALSE); 
            fStack[fn]:=f
          END
        END;
        ip:=ip^.next
      END
    END IntersectEdgeWithMap;
    
  BEGIN
    (* --- initializes the list of intersection points --- *)
    lip := InitializeLIP();

    earc := GetArcGeometry(e);

Wr.PutText(Stdio.stdout," Em IntersectBetweenTwoEdgeElem --> earc = ");
SMGeo.PrintArc(Stdio.stdout,earc);
Wr.PutText(Stdio.stdout,"\n");
Wr.Flush(Stdio.stdout);

    TYPECASE elem OF 
    | T(m) => IntersectEdgeWithMap();         
    | Face(f) => f.walkOn(IntersectTwoCorners, FALSE); 
    | Border(b) => b.walkOn(IntersectTwoCorners, FALSE); 
    ELSE
    END;

    RETURN lip
  END IntersectEdgeWithElement;

PROCEDURE NumerateMap(self: T) =
  VAR cnum,vnum,enum,bnum,fnum : CARDINAL;
      cnt : SMTop.TCounter;
      vStack : VStack;
      eStack : EStack;
      bStack : BStack;
      fStack : FStack;
  
  PROCEDURE VisitAndNumerate(ic: Corner) = 
    BEGIN
      (* --- numerates the corner --- *) 
      INC(cnum);
      ic.setNum(cnum);
      
      (* --- marks and numerates vertex, edge and face --- *)
      IF NOT ic.isRing() THEN 
        WITH 
          v = ic.org(),
          vn = v.getNum()
        DO 
          (* --- checks if the vertex's number is up-to-date --- *)
          IF NOT IsOutOfStackRange(vStack,vn) AND vStack[vn] # v THEN
            INC(vnum);
            v.setNum(vnum);
            IF IsOutOfStackRange(vStack,vnum) THEN DoubleStackSize(vStack) END;
            vStack[vnum]:=v
          END
        END
      END; 
      IF NOT ic.isIsolatedVertex() THEN 
        WITH 
          e = ic.edg(), 
          en = e.getNum()
        DO 
          (* --- checks if the edge's number is up-to-date --- *)
          IF NOT IsOutOfStackRange(eStack,en) AND eStack[en] # e THEN
            INC(enum);
            e.setNum(enum);
            IF IsOutOfStackRange(eStack,enum) THEN DoubleStackSize(eStack) END;
            eStack[enum]:=e
          END
        END
      END; 
      WITH 
        b = ic.borderOf(),
        bn = b.getNum()
      DO 
        (* --- checks if the border's number is up-to-date --- *)
        IF NOT IsOutOfStackRange(bStack,bn) AND bStack[bn] # b THEN
          INC(bnum);
          b.setNum(bnum);
          IF IsOutOfStackRange(bStack,bnum) THEN DoubleStackSize(bStack) END;
          bStack[bnum]:=b
        END
      END;
      WITH 
        f = ic.faceOf(),
        fn = f.getNum()
      DO 
        (* --- checks if the face's number is up-to-date --- *)
        IF NOT IsOutOfStackRange(fStack,fn) AND fStack[fn] # f THEN
          INC(fnum);
          f.setNum(fnum);
          IF IsOutOfStackRange(fStack,fnum) THEN DoubleStackSize(fStack) END;
          fStack[fnum]:=f
        END
      END
    END VisitAndNumerate;

  BEGIN

Wr.PutText(Stdio.stdout,"\n\n %%%%%%%%%% Entrou em NumerateMap %%%%%%%%%%%% \n\n ");
Wr.Flush(Stdio.stdout);
    
    vStack := NEW(VStack, StackSize);
    eStack := NEW(EStack, StackSize);
    bStack := NEW(BStack, StackSize);
    fStack := NEW(FStack, StackSize);
    
    cnum:=0; vnum:=0; enum:=0;  bnum:=0;  fnum:=0;
    self.walkOn(VisitAndNumerate);
    cnt.NC:=cnum; cnt.NB:=bnum; cnt.NF:=fnum;
    self.setTCounter(cnt);
    self.NV:=vnum; self.NE:=enum; 
    
    self.ValidNumber:=TRUE;    

Wr.PutText(Stdio.stdout,"\n\n %%%%%%%%%% Saiu de NumerateMap %%%%%%%%%%%% ");
Wr.PutText(Stdio.stdout,"NF = "&Fmt.Int(fnum)&"  NB = "&Fmt.Int(bnum)&" NC = "&Fmt.Int(cnum)&"  NV = "&Fmt.Int(vnum)&" NE = "&Fmt.Int(enum)&"\n\n");
Wr.Flush(Stdio.stdout);
    
  END NumerateMap;

PROCEDURE ReadMap(self: T; name: TEXT) =
  CONST dig = SET OF CHAR{'0'..'9'};
  VAR rd : FileRd.T;
      vStack : VStack;
      eStack : EStack;
      cnt    : SMTop.TCounter;
      
  PROCEDURE ReadVertices() = 
    BEGIN

Wr.PutText(Stdio.stdout,"Inicio de ReadVertice --- ");
Wr.Flush(Stdio.stdout);

      FileFmt.ReadHeader(rd,"Vertices Data","");
      EVAL FileFmt.ReadComment(rd,'#');
      FGet.Skip(rd);
      WHILE Rd.GetChar(rd) IN dig DO 
        Rd.UnGetChar(rd);
        WITH  vnum = FGet.Int(rd) DO 
          IF vStack[vnum] # NIL THEN
            vStack[vnum].setNum(vnum);
            vStack[vnum].setStyle(FGet.Int(rd));
            vStack[vnum].setGeom(SMGeo.ReadPoint(rd))
          END;
          
Wr.PutText(Stdio.stdout,"Leu vertice "&Fmt.Int(vnum)&" = ");
SMPoint.PrintCpoint(Stdio.stdout,vStack[vnum].getGeom()^);
Wr.PutText(Stdio.stdout,"\n");
Wr.Flush(Stdio.stdout);

        END;
        
        (* --- ignores the equivalent Spoint --- *)
        FGet.Skip(rd);
        FGet.Match(rd,"<=>");
        EVAL SMPoint.ReadSpoint(rd);

        FGet.EOL(rd);
        FGet.Skip(rd)
      END;
      Rd.UnGetChar(rd);
      FileFmt.ReadFooter(rd,"Vertices Data")
    END ReadVertices;
   
  PROCEDURE ReadEdges() = 
    BEGIN
      FileFmt.ReadHeader(rd,"Edges Data","");
      EVAL FileFmt.ReadComment(rd,'#');
      Lex.Skip(rd);
      WHILE Rd.GetChar(rd) IN dig DO 
        Rd.UnGetChar(rd);
        WITH  enum = FGet.Int(rd) DO 
          IF eStack[enum] # NIL THEN
            eStack[enum].setNum(enum);
            eStack[enum].setStyle(FGet.Int(rd));
            eStack[enum].setGeom(SMGeo.ReadCircle(rd));
          END;

Wr.PutText(Stdio.stdout,"Leu edge "&Fmt.Int(enum)&" \n");    
Wr.Flush(Stdio.stdout);

        END;
        
        FGet.EOL(rd);
        Lex.Skip(rd)
      END;
      Rd.UnGetChar(rd);
      FileFmt.ReadFooter(rd,"Edges Data")
    END ReadEdges;
   
  BEGIN
Wr.PutText(Stdio.stdout,"Entrei em ReadMap \n");    
Wr.Flush(Stdio.stdout);

    rd:=FileRd.Open(name);

    EVAL FileFmt.ReadComment(rd,'#');  (* ---  discards the title   --- *)
    EVAL FileFmt.ReadComment(rd,'#');  (* --- discards the comments --- *)
    
    (* --- reads the element's counter  --- *) 
    cnt.NC := NGet.Int(rd,"Corners");  FGet.EOL(rd);
    self.NV:= NGet.Int(rd,"Vertices"); FGet.EOL(rd); 
    self.NE:= NGet.Int(rd,"Edges");   FGet.EOL(rd);
    cnt.NB := NGet.Int(rd,"Borders");  FGet.EOL(rd);
    cnt.NF := NGet.Int(rd,"Faces");  FGet.EOL(rd);
    EVAL FileFmt.ReadComment(rd,'#');  (* --- discards a blank line --- *)
    
    (* --- initializes the topological counter's --- *)
    self.setTCounter(cnt);

Wr.PutText(Stdio.stdout,"   NV = "&Fmt.Int(self.NV)&"   NE = "&Fmt.Int(self.NE)&"\n");
Wr.Flush(Stdio.stdout);

    (* --- initializes stack in --- *)
    vStack:=NEW(VStack,self.NV+1);
    eStack:=NEW(EStack,self.NE+1);
    
    (* --- reads the topology --- *)
    FileFmt.ReadHeader(rd,"Topology","");

Wr.PutText(Stdio.stdout,"Antes de ReadCorners \n");    
Wr.Flush(Stdio.stdout);
    
    NARROW(self, SMTop.Map).read(rd, vStack, eStack);
    
    EVAL FileFmt.ReadComment(rd,'#');  (* ---  discards the blank line --- *)
    FileFmt.ReadHeader(rd,"Features","");
    
    ReadVertices();
    ReadEdges();

    FileFmt.ReadFooter(rd,"Features");

Wr.PutText(Stdio.stdout,"<<<< Encerrou leitura >>>> \n");    
Wr.Flush(Stdio.stdout);

  END ReadMap;


(* =================================================== *)
(*       Internal procedures used by WriteMap          *)         
(* =================================================== *)
PROCEDURE NumDigits(n: CARDINAL) : CARDINAL = 
  VAR w: CARDINAL:=1;
  BEGIN
    WHILE n>9 DO INC(w); n:=n DIV 10 END;
    RETURN w
  END NumDigits;

PROCEDURE WriteMap(self: T; name: TEXT; comment: TEXT) = 
  CONST 
    HeaderVertex = "number,   style,    geometry";
    HeaderEdge   = "number,   style,    geometry";
  VAR wr  : FileWr.T;
      vWidth : CARDINAL := NumDigits(self.NV);
      eWidth : CARDINAL := NumDigits(self.NE);
      
      vStack: VStack;
      eStack: EStack;
  
  BEGIN
    wr:=FileWr.Open(name);
    
Wr.PutText(Stdio.stdout,"\n<<<< Iniciando Escrita >>>> \n");    
Wr.PutText(Stdio.stdout,"Antes da numeracao --> ");    
WITH cnt=self.getTCounter() DO 
Wr.PutText(Stdio.stdout,"NC = "&Fmt.Int(cnt.NC)&"  NV = "&Fmt.Int(self.NV)&"  NE = "&Fmt.Int(self.NE)&"  NB = "&Fmt.Int(cnt.NB)&"  NF = "&Fmt.Int(cnt.NF)&"\n");
Wr.Flush(Stdio.stdout);
END;

    IF NOT self.ValidNumber THEN 
      self.numerate()
    END;

WITH cnt=self.getTCounter() DO 
Wr.PutText(Stdio.stdout,"NC = "&Fmt.Int(cnt.NC)&"  NV = "&Fmt.Int(self.NV)&"  NE = "&Fmt.Int(self.NE)&"  NB = "&Fmt.Int(cnt.NB)&"  NF = "&Fmt.Int(cnt.NF)&"\n");
Wr.Flush(Stdio.stdout);
END;

Wr.PutText(Stdio.stdout,"Terminou numeracao\n");    
Wr.Flush(Stdio.stdout);

    (* --- initializes the stack of vertices and edges --- *)
    vStack:=NEW(VStack, self.NV+1);
    eStack:=NEW(EStack, self.NE+1);

    (* --- writes title and comments --- *)
    FileFmt.WriteComment(wr,"<<<< Spherical Map - Version "&SMVersion&" >>>>",'#');
    IF NOT Text.Empty(comment) THEN 
      FileFmt.WriteComment(wr,comment,'#');
    END;

Wr.Flush(wr);
Wr.PutText(Stdio.stdout,"Escreveu cabecalhos \n");    
Wr.Flush(Stdio.stdout);
    
    (* --- writes the element's counter --- *) 
    WITH cnt = self.getTCounter() DO 
      NPut.Int(wr,Fmt.Pad("Corners ",8),cnt.NC);  FPut.EOL(wr);
      NPut.Int(wr,Fmt.Pad("Vertices",8),self.NV);  FPut.EOL(wr); 
      NPut.Int(wr,Fmt.Pad("Edges   ",8),self.NE);  FPut.EOL(wr);
      NPut.Int(wr,Fmt.Pad("Borders ",8),cnt.NB);  FPut.EOL(wr);
      NPut.Int(wr,Fmt.Pad("Faces   ",8),cnt.NF);  FPut.EOL(wr);
    END;
    
    (* --- writes topology --- *)
    NARROW(self, SMTop.Map).write(wr, vStack, eStack);
    
    (* --- writes features of vertices and edges --- *)
    FileFmt.WriteComment(wr," ",'#');    (* --- writes a blank line --- *)
    FileFmt.WriteHeader(wr,"Features","");
    FileFmt.WriteHeader(wr,"Vertices Data","");
    FileFmt.WriteComment(wr,HeaderVertex,'#');

    (* --- writes the vertices --- *)
    FOR i:=0 TO self.NV DO 
      WITH v = vStack[i] DO  
        IF v # NIL THEN 
          Wr.PutText(wr,"    "&Fmt.Pad(Fmt.Int(i),vWidth)&"    ");
          Wr.PutText(wr,"    "&Fmt.Int(v.getStyle())&"      ");
          
          (* writes Cpoint's Plucker coefficients and its equivalent Spoint *)
          WITH p = v.getGeom() DO 
            SMPoint.PrintCpoint(wr,p^);
            Wr.PutText(wr,"   <=>   ");
            SMPoint.PrintSpoint(wr,SMPoint.CToS(p^),8);
          END;
          FPut.EOL(wr)
        END
      END;
    END;
    FileFmt.WriteFooter(wr,"Vertices Data");

    (* --- writes the edges --- *)
    FileFmt.WriteHeader(wr,"Edges Data","");
    FileFmt.WriteComment(wr,HeaderEdge,'#');
    FOR i:=0 TO self.NE DO 
      WITH e = eStack[i] DO  
        IF e # NIL THEN 
          Wr.PutText(wr,"   "&Fmt.Pad(Fmt.Int(i),eWidth)&"    ");
          Wr.PutText(wr,"   "&Fmt.Int(e.getStyle())&"     ");
          WITH sc = e.getGeom() DO SMCircle.Print(wr,sc^) END;
          FPut.EOL(wr)
        END
      END;
    END;
    FileFmt.WriteFooter(wr,"Edges Data");
    
    FileFmt.WriteFooter(wr,"Features");
    Wr.Close(wr);
  END WriteMap;

PROCEDURE DrawMap(self: T; name: TEXT) = 
  VAR sd: SMDraw.T;
      params : SMDraw.Atributes;

      vStack: VStack;
      eStack: EStack;

  PROCEDURE DrawCorner(c: Corner) = 
    BEGIN
      IF c.isIsolatedVertex() THEN 
        WITH vn = c.org().getNum() DO 
          (* --- checks if that vertex wasn't used yet --- *)
          IF vStack[vn] = NIL THEN 
            WITH sp=SMPoint.CToS(GetVertexGeometry(c)^) DO 
              sd.drawPoint(sp,params);
            END;
            vStack[vn]:=c.org()
          END
        END
      ELSE 
        WITH en = c.edg().getNum() DO 
          (* --- checks if that edge wasn't used yet --- *)
          IF eStack[en] = NIL THEN 
            IF c.isRing() THEN 
              WITH circ=c.edg().getGeom() DO 
                sd.drawCircle(circ^,params);
              END;
            ELSE
              sd.drawSegment(c.getGeoOfArc(c.cSym()),params);
            END;
            eStack[en]:=c.edg()
          END
        END
      END
    END DrawCorner;
  
  BEGIN
    sd:=NEW(SMDraw.T).init(name);

Wr.PutText(Stdio.stdout,"Inicializou FileDraw \n");    
Wr.Flush(Stdio.stdout);

    IF NOT self.ValidNumber THEN 
      self.numerate()
    END;

Wr.PutText(Stdio.stdout,"Saiu de Numeracao \n");    
Wr.Flush(Stdio.stdout);


    (* --- initializes the stack of vertices and edges --- *)
    vStack:=NEW(VStack, self.NV+1);
    eStack:=NEW(EStack, self.NE+1);

    (* --- initializes params; must be replaced by customer's parametrization --- *)
    params.color:=Color{0.0,0.0,0.0};
    params.width:=0.3;
    params.colorfill:=Color{0.0,0.0,0.0};
    params.radius:=0.7;

    (* --- writes corners and builds stack with vertices, edges and faces --- *)
    self.walkOn(DrawCorner);
    
    sd.close();
  END DrawMap;


BEGIN
  RefPoint := NEW(InterPoint);
  RefPoint^.p:=SMGeo.NorthPole; 
  RefPoint^.which:=NIL;
END SMap.