MODULE TMC;
(*
   Created in Jan 21, 1997 by Marcus Vinicius A. Andrade
   Lasted edited in May 6, 1998 by Marcus Vinicius A. Andrade            
*)
  
FROM SMGeo IMPORT Sign;
IMPORT TMBorder, SetOfBorders, TMCFeat, FileRd, FileWr, FileFmt, NGet, NPut, FGet, FPut, Fmt, Rd, Wr, Stdio, Extras;

REVEAL 
  Corner = Public BRANDED OBJECT 
     onext : Corner;      (* the next counterclockwise corner orbiting the vertex *)
     lnext : Corner;      (* the next corner on the border containing the corner  *)
     border: Border;      (* the descriptor of the border containing the corner   *)
  METHODS 
    bInsert(b: Border) := BInsert;
    bRemove() := BRemove;
    setONext(c: Corner) := SetONext;
    setLNext(c: Corner) := SetLNext;
  OVERRIDES 
    createIsolatedVertex := CreateIsolatedVertex;
    createEdge := CreateEdge;
    createOval := CreateOval;
    isIsolatedVertex := IsIsolatedVertex;
    isOval := IsOval;
    org := Org;
    halfEdge := HEdge;
    borderOf := BorderOf;
    left := Left;
    oNext := ONext;
    oPrev := OPrev;
    lNext := LNext;
    lPrev := LPrev;
    sym := Sym;

    splice := Splice;
  END; 

  Border = PublicBorder BRANDED OBJECT 
    face : Face;          (* left face to this border                  *)
    desc : Corner;        (* the corner representing this border       *)
    nc   : CARDINAL;      (* number of corners refering to this record *)
  METHODS 
    init(c: Corner) : Border := InitBorder;   (* creates a "new" border with one corner "c"  *)
    insertCorner(c: Corner) := InsertCorner;  (* inserts the corner "c" in the border        *)
    insertInFace(f: Face) := InsertInFace;    (* inserts the border in face "f"              *)
    removeFromItsFace() := RemoveFromItsFace; (* removes the border from its face            *)
    updateDesc(d: Corner) := UpdateDesc;      (* visits all corners in the border setting their 
                                                 field "border" to "d";                   *)
  OVERRIDES
    borderDesc := BorderDesc;
    faceOf := FaceOfBorder;
    removeCorner := RemoveCorner;
    walkOn := WalkOnBorder;
  END;
  
  (* -----------------------------------------------------------------------
     The face's boundary will be implemented as "SET of Border", where we 
     will use the library "SET" provided by a Modula-3 package implemented 
     as a linked list.
     ----------------------------------------------------------------------- *)

  Face = PublicFace BRANDED OBJECT 
    sb   : SetOfBorders.T;    (* set of borders constituting the face's boundary *)
  METHODS 
    init() : Face := InitFace;                 (* creates a new face with no border         *)
    isFaceEmpty() : BOOLEAN := IsFaceEmpty;    (* returns TRUE fs the face has NO border    *)
    insertBorder(b: Border) := InsertBorder;   (* inserts "b" in the face (set of borders)  *) 
    removeBorder(b: Border) := RemoveBorder;   (* removes "b" from the face (set of borders *)
  OVERRIDES 
    genus := Genus;
    bordersOf := BordersOf;
    transferBorder := TransferBorder;
    mergeFaces := MergeFaces;
    walkOn := WalkOnFace;
  END;

  Map = PublicMap BRANDED OBJECT 
    f        : Face;      (* reference face of the map            *)
    c        : Corner;    (* reference corner of the map          *)    
    NC,NB,NF : CARDINAL;  (* number of corners, borders and faces *)
  OVERRIDES 
    init := InitMap;
    getTCounter := GetTCounter;    
    setTCounter := SetTCounter;    
    refFace := RefFace;
    setRefFace := SetRefFace;
    refCorner := RefCorner;
    setRefCorner := SetRefCorner;
    walkOn := WalkOnMap;
    read := ReadTop;
    write := WriteTop;
  END;

(* ============================================================ *)
(*  Definition of types and procedures to manipulate the queues *)
(*  of Faces and Corners that were seen and maybe not visited   *)
(*  yet during enumeration of map.                              *)
(* ============================================================ *)
CONST 
  SFSize = 128;   (* initial face's stack size   *)
  SCSize = 1024;  (* initial corner's stack size *)

REVEAL 
  QueueOfCorners = BRANDED REF RECORD   
    vet : REF ARRAY OF Corner; (* queue storing the corners       *)
    bot,top : CARDINAL;        (* the top and bottom of the queue *)
  END;

  QueueOfFaces = BRANDED REF RECORD   
    vet : REF ARRAY OF Face;   (* queue storing the faces         *)
    bot,top : CARDINAL;        (* the top and bottom of the queue *)
  END;

PROCEDURE QInit(queue: REFANY) =
  BEGIN
    TYPECASE queue OF 
    | QueueOfFaces(fqueue)   => BEGIN 
                                  fqueue^.vet:=NEW(REF ARRAY OF Face,SFSize);
                                  fqueue^.top:=0;
                                  fqueue^.bot:=0
                                END;
    | QueueOfCorners(cqueue) => BEGIN 
                                  cqueue^.vet:=NEW(REF ARRAY OF Corner,SCSize);
                                  cqueue^.top:=0;
                                  cqueue^.bot:=0
                                END;
    ELSE 
    END; 
  END QInit;

PROCEDURE QIsEmpty(queue: REFANY) : BOOLEAN =
  BEGIN
    TYPECASE queue OF 
    | QueueOfFaces(fqueue)   => RETURN fqueue^.top = fqueue^.bot;
    | QueueOfCorners(cqueue) => RETURN cqueue^.top = cqueue^.bot;
    ELSE
    END
  END QIsEmpty;

PROCEDURE QIsFull(queue: REFANY) : BOOLEAN = 
  BEGIN
    TYPECASE queue OF 
    | QueueOfFaces(fqueue)   => RETURN fqueue^.top = NUMBER(fqueue^.vet^)-1;
    | QueueOfCorners(cqueue) => RETURN cqueue^.top = NUMBER(cqueue^.vet^)-1;
    ELSE
    END
  END QIsFull;

PROCEDURE DoubleQSize(queue: REFANY) = 
  BEGIN
    TYPECASE queue OF 
    | QueueOfFaces(fqueue)   => BEGIN
                                  WITH
                                    sz = NUMBER(fqueue^.vet^),
                                    szn = 2*sz,
                                    newvet = NEW(REF ARRAY OF Face,szn)
                                  DO
                                    SUBARRAY(newvet^,0,sz) := fqueue^.vet^;
                                    fqueue^.vet:=newvet
                                  END;
                                END;
    | QueueOfCorners(cqueue) => BEGIN 
                                  WITH
                                    sz = NUMBER(cqueue^.vet^),
                                    szn = 2*sz,
                                    newvet = NEW(REF ARRAY OF Corner,szn)
                                  DO
                                    SUBARRAY(newvet^,0,sz) := cqueue^.vet^;
                                    cqueue^.vet:=newvet
                                  END;
                                END
    ELSE
    END;
  END DoubleQSize;


PROCEDURE QInsert(elem : REFANY; queue: REFANY) =
  BEGIN
    TYPECASE queue OF 
    | QueueOfFaces(fqueue)   => BEGIN
                                  IF QIsFull(fqueue) THEN DoubleQSize(fqueue)
                                  ELSE
                                    fqueue^.vet[fqueue^.top]:=NARROW(elem,Face);
                                    INC(fqueue^.top)
                                  END;
                                END;
    | QueueOfCorners(cqueue) => BEGIN 
                                  IF QIsFull(cqueue) THEN DoubleQSize(cqueue)
                                  ELSE
                                    cqueue^.vet[cqueue^.top]:=NARROW(elem,Corner);
                                    INC(cqueue^.top)
                                  END;
                                END
    ELSE
    END;
  END QInsert;

PROCEDURE QRemove(queue: REFANY) : REFANY =
  BEGIN
    TYPECASE queue OF 
    | QueueOfFaces(fqueue)   => BEGIN
                                  IF fqueue^.top = fqueue^.bot THEN 
                                    (* queue is empty *)
                                  ELSE
                                    WITH
                                      bot = fqueue^.bot,
                                      elem = fqueue^.vet[bot]
                                    DO
                                      INC(bot);
                                      RETURN elem
                                    END 
                                  END;
                                END;
    | QueueOfCorners(cqueue) => BEGIN 
                                  IF cqueue^.top = cqueue^.bot THEN 
                                    (* queue is empty *)
                                  ELSE
                                    WITH
                                      bot = cqueue^.bot,
                                      elem = cqueue^.vet[bot]
                                    DO
                                      INC(bot);
                                      RETURN elem
                                    END 
                                  END;
                                END;
    ELSE 
    END;
  END QRemove;

PROCEDURE QRelease(queue: REFANY; PUnmark: PROCEDURE (elem: REFANY)) =
  BEGIN
    TYPECASE queue OF 
    | QueueOfFaces(fqueue)   => BEGIN
                                  FOR i:=0 TO NUMBER(fqueue^.vet^)-1 DO 
                                    IF fqueue^.vet[i] # NIL  THEN 
                                      PUnmark(fqueue^.vet[i])
                                    END
                                  END;
                                END;
    | QueueOfCorners(cqueue) => BEGIN
                                  FOR i:=0 TO NUMBER(cqueue^.vet^)-1 DO  
                                    IF cqueue^.vet[i] # NIL THEN 
                                      PUnmark(cqueue^.vet[i])
                                    END
                                  END;
                                END;
    ELSE
    END
  END QRelease;


(* -------------------------------------------- *)
(*                Internal procedures           *)
(* -------------------------------------------- *)            

PROCEDURE SpliceSplit(c,d : Corner) =
  BEGIN
    WITH 
      con = c.oNext(),
      don = d.oNext(),
      cbp = c.lPrev(),
      dbp = d.lPrev()
    DO 
      c.onext := don;
      d.onext := con;
      cbp.lnext := d;
      dbp.lnext := c
    END;
  END SpliceSplit;

(* -------------------------------------------- *)
(*         Internal methods OF Corner           *)
(* -------------------------------------------- *)            

PROCEDURE BInsert(self: Corner; b: Border) =
  BEGIN
    self.border := b
  END BInsert;

PROCEDURE BRemove(self: Corner) =
  BEGIN
    self.border := NIL 
  END BRemove;

PROCEDURE SetONext(self: Corner; c: Corner) = 
  BEGIN
    self.onext:=c
  END SetONext;

PROCEDURE SetLNext(self: Corner; c: Corner) = 
  BEGIN
    self.lnext:=c
  END SetLNext;


(*
PROCEDURE SpliceSplit(c,d : Corner) =
  (* "d" will be inserted in between "c" and "c.oPrev", i.e., (in 
     counterclockwise sense) "d" will be inserted before "c" and after c.oPrev() *)
      
  BEGIN
    WITH 
      cop = c.oPrev(),
      cop2 = cop.oPrev(),
      cs = c.sym(),
      ds = d.sym()
    DO 
      cop.onext := d;
      d.onext := c;
      cs.lnext := d;
      ds.lnext := cop;
      
      IF ds = c THEN  
        (* --- will be formed a counterclockwise loop starting at "d" --- *)
        cs.lnext:=ds;
        d.lnext:=d;
      ELSIF ds = cop THEN 
        (* --- will be formed a clockwise loop starting at "d" --- *)
        d.lnext:= cop2;
      END
    END;
  END SpliceSplit;
*)

(* -------------------------------------------------- *)
(*                METHODS OF Corner                   *)
(* -------------------------------------------------- *)            
PROCEDURE CreateIsolatedVertex(self: Corner): Corner = 
  BEGIN
    self.initVertex();
    self.onext:= self;
    self.lnext:= self;
    WITH 
      fs = NEW(Face).init(),
      bs = NEW(Border).init(self)
    DO
      fs.insertBorder(bs)
    END;
    RETURN self
  END CreateIsolatedVertex;

PROCEDURE CreateEdge(self: Corner): Corner = 
  BEGIN
    self.initHalfEdge();
    self.initVertex();
    WITH c = NEW(Corner) DO
      c.initHalfEdge();
      c.initVertex();
      self.onext:= self;
      c.onext := c;
      self.lnext:= c;
      c.lnext := self;
      WITH
        fs = NEW(Face).init(),
        bs = NEW(Border).init(self)
      DO
        fs.insertBorder(bs);
        bs.insertCorner(c);
        (* --- the corners "e" and "e.sym" are in the same border --- *)
        INC(bs.nc) 
      END;
      RETURN self
    END
  END CreateEdge;

PROCEDURE CreateOval(self: Corner): Corner = 
  BEGIN
    self.initHalfEdge();
    WITH c = NEW(Corner) DO
      c.initHalfEdge();
      self.onext:= c;
      c.onext := self;
      self.lnext:= self;
      c.lnext := c;
      WITH
        fs = NEW(Face).init(),
        bs = NEW(Border).init(self),
        fc = NEW(Face).init(),
        bc = NEW(Border).init(c)
      DO
        fs.insertBorder(bs);
        fc.insertBorder(bc)
      END;
      RETURN self
    END
  END CreateOval;

PROCEDURE IsIsolatedVertex(self: Corner) : BOOLEAN = 
  BEGIN
    RETURN (self.halfEdge() = NIL)
  END IsIsolatedVertex;

PROCEDURE IsOval(self : Corner) : BOOLEAN =
  BEGIN
    RETURN (self.vertex() = NIL)
  END IsOval;
  
PROCEDURE Org(self: Corner) : Vertex = 
  BEGIN
    RETURN NARROW(self,TMCFeat.T).vertex()
  END Org;

PROCEDURE HEdge(self: Corner) : HalfEdge = 
  BEGIN
    RETURN NARROW(self,TMCFeat.T).halfEdge()
  END HEdge;

PROCEDURE ONext(self: Corner) : Corner = 
  BEGIN
    RETURN self.onext
  END ONext;

PROCEDURE OPrev(self: Corner) : Corner = 
  BEGIN
    RETURN self.sym().lnext
  END OPrev;

PROCEDURE LNext(self: Corner) : Corner = 
  BEGIN
    RETURN self.lnext
  END LNext;

PROCEDURE LPrev(self: Corner) : Corner = 
  BEGIN
    RETURN self.onext.sym()
  END LPrev;

PROCEDURE BorderOf(self: Corner) : Border =
  BEGIN
    RETURN self.border
  END BorderOf;

PROCEDURE Left(c: Corner) : Face =
  BEGIN
    RETURN c.border.face
  END Left;

PROCEDURE Sym(self: Corner) : Corner =
  BEGIN
    RETURN self.lnext.onext
  END Sym;

PROCEDURE Splice(self: Corner; c: Corner) = 
  BEGIN
    IF NOT self.isOval() AND NOT c.isOval() THEN 
      WITH
        bs = self.borderOf(),
        fs = bs.faceOf(),
        bc = c.borderOf(),
        fc = bc.faceOf()
      DO
       IF fs = fc THEN
          SpliceSplit(self,c);
          WITH nfs = NEW(Face).init() DO
            bs.desc:=self;
            nfs.transferBorder(bs);
            IF bs # bc THEN 
              (* ----------------------------------------------------------- *)
              (* joins the borders of "self" and "bc" and updates the border *) 
              (* field of the corners in the new border                      *)
              (* ----------------------------------------------------------- *)
              bs.updateDesc(bs.desc);
              bc.removeFromItsFace();

              (* nfs.transferBorder(bc);
              JoinBorders(bs,bc);  *)
            ELSE
              (* ---------------------------------------------------------- *)
              (* creates a new face and new border descripted by "c"; also, *)
              (* updates the field "border" of the corners in the new border*)
              (* ---------------------------------------------------------- *)

              WITH 
                nbc = NEW(Border).init(c),  
                nfc = NEW(Face).init() 
              DO
                nfc.insertBorder(nbc);
                SplitBorders(bs,nbc)
              END
            END
          END
        END    
      END  
    END
  END Splice;
  
PROCEDURE Split(self: Corner; c: Corner) =
  BEGIN
    IF self.org() = c.org() THEN 
      WITH
        bs = self.borderOf(),
        fs = bs.faceOf(),
        bc = c.borderOf(),
        fc = bc.faceOf()
      DO
        SpliceSplit(self,c);
        fs.removeBorder(bs);
        WITH
          nfs = NEW(Face).init(),
          nbs = NEW(Border).init(self)
        DO
          nfs.insertBorder(nbs);
          IF bs # bc THEN 
          (* ------------------------------------------------------- *)
          (* It means that "self" and "c" are in borders of different*)
          (* faces; so, splits the common vertex, creates a new face *)
          (* with one border decribed by "self"; the "old" borders   *)
          (* records are removed from theirs faces.                  *)
          (* ------------------------------------------------------- *)
            fc.removeBorder(bc);
            nbs.updateDesc(nbs.borderDesc())
          ELSE 
          (* ------------------------------------------------------- *)
          (* "self" and "c" are in a same borders; so  splits that   *)
          (* border creating two new borders in the common face: one *)
          (* described by "self" and another one described by "c";   *)
          (* also, updates the border's descriptor of the corners in *)
          (* each border and the corner's counter                    *)
          (* ------------------------------------------------------- *)
            WITH
              nbc = NEW(Border).init(c)
            DO
              nfs.insertBorder(nbc);
              nbs.updateDesc(nbs.borderDesc());
              nbc.updateDesc(nbc.borderDesc());
            END
          END;
        END
      END
    END
  END Split;

(* --------------------------------------------- *)
(*      Exported procedure involving Corners     *)
(* --------------------------------------------- *)            
PROCEDURE DropOnEdge(c: Corner) : Corner =
(* 
   Creates a "new" vertex on an edge; it corresponds to create a 
   pair of corners "d" and "ds" where "d" is inserted just after 
   "c" and "ds" after "cs". After this operation, "d" pass to be 
   "c.sym" and "ds" pass to be "cs.sym". 
   
   See figure:

   
    con\.__  __.__  __./
       / c   ds d   cs \    
          
*)

  BEGIN
    IF c.isOval() THEN 
      (* ----------------------------------------------- *)
      (* if "c" corresponds to an oval, just transforms  *)
      (* it into a loop creating a vertex on the oval    *)
      (* ----------------------------------------------- *)
      c.initVertex();
      c.sym().setVertex(c.org());
      RETURN c;
    ELSE 
      WITH 
        d = NEW(Corner).createOval(),
        ds = d.sym(),
        cs   = c.sym(),
        cbn = c.lNext(),
        csbn = cs.lNext()
      DO 
        c.lnext := d;
        cs.lnext := ds;
        d.lnext := cbn;
        ds.lnext:= csbn;
        (* --- inserts "d" and "ds" in their borders --- *)
        WITH 
          b=c.borderOf(),
          bs=cs.borderOf()
        DO 
          b.insertCorner(d);
          bs.insertCorner(ds);
        END;
        (* --- sets "d.org" and "ds.org" to a new vertex --- *)
        d.initVertex();
        ds.setVertex(d.org());
        RETURN d
      END;
    END
  END DropOnEdge;

(* --------------------------------------------- *)
(*       Internal procedures of Border           *)
(* --------------------------------------------- *)            
PROCEDURE JoinBorders(b1,b2: Border) = 
  (* joins the two borders updating the border field of the corners 
     in the smallest border *)
  VAR Mb,mb : Border;
  BEGIN 
    IF b1.nc >= b2.nc THEN 
      Mb:=b1;
      mb:=b2
    ELSE
      Mb:=b2;
      mb:=b1
    END;
    Mb.updateDesc(mb.borderDesc());
  END JoinBorders;

PROCEDURE SplitBorders(b1,b2: Border) = 
  BEGIN
    b1.updateDesc(b1.borderDesc());
    b2.updateDesc(b2.borderDesc());
  END SplitBorders;


(* --------------------------------------------- *)
(*                METHODS OF Border              *)
(* --------------------------------------------- *)            

PROCEDURE UpdateDesc(self: Border; d: Corner) =
  VAR c: Corner;
  BEGIN
    self.nc:=0;
    c:=d;
    REPEAT 
      c.border := self;
      INC(self.nc);
      c:=c.lNext()
    UNTIL c = d;
  END UpdateDesc;

PROCEDURE InitBorder(self: Border; c: Corner): Border =
  BEGIN
    self.face:=NIL;
    self.desc:=c;
    self.nc:=1;
    c.bInsert(self);
    RETURN self
  END InitBorder;

PROCEDURE BorderDesc(self: Border) : Corner =
  BEGIN
    RETURN self.desc
  END BorderDesc;

PROCEDURE FaceOfBorder(self: Border) : Face =
  BEGIN
    RETURN self.face
  END FaceOfBorder;

PROCEDURE InsertCorner(self: Border; c: Corner) =
  BEGIN
    c.bInsert(self);
    self.nc := self.nc + 1
  END InsertCorner;

PROCEDURE RemoveCorner(self: Border; c: Corner) =
  BEGIN
    c.bRemove();
    DEC(self.nc);
    IF self.nc = 0 THEN 
     (* ------------------------------------------ *) 
     (*  there is no more corners in that border;  *)
     (*  so, removes it from its face              *)
     (* ------------------------------------------ *) 
      self.faceOf().removeBorder(self);
    ELSIF self.borderDesc() = c THEN
     (* --------------------------------------------------------- *) 
     (* the corner being removed is the descriptor of the border; *) 
     (* so, sets another corner as the border descriptor          *)
     (* --------------------------------------------------------- *) 
      self.desc:=c.lNext();
    END;
  END RemoveCorner;

PROCEDURE InsertInFace(self: Border; f: Face) =
  BEGIN
    f.insertBorder(self);
    self.face:=f
  END InsertInFace;

PROCEDURE RemoveFromItsFace(self: Border) =
  BEGIN
    WITH f = self.faceOf() DO
      f.removeBorder(self);
    END
  END RemoveFromItsFace;

PROCEDURE WalkOnBorder(self: Border; P: VisitProc; GetFaces: BOOLEAN:=TRUE; qftv: QueueOfFaces:=NIL) = 
  VAR c,cnext,d: Corner;
  BEGIN
    d:=self.borderDesc();
    c:=d;
    REPEAT 
     (* we have to get c.lnext before performing P(c) because in case of 
        IntersectionAndBreak, the procedure "P" will insert a new corner 
        after "c" and this new corner can not be checked again *)

      cnext := c.lNext();
      P(c);
        
      (* --- writes an indicator to user --- *)
      WITH num=c.getNum() DO 
        IF num MOD 10 = 0 THEN 
          Wr.PutText(Stdio.stdout,".");
          Wr.Flush(Stdio.stdout);
        END
      END;
        
      IF GetFaces THEN
        c.left().mark();
        (* === stores the neighbor face for future visit === *)
        WITH f = c.sym().left() DO 
          IF NOT f.isMarked() THEN 
            QInsert(f,qftv);
            f.mark()
          END
        END
      END;
      c:=cnext
    UNTIL c = d;
  END WalkOnBorder;

(* --------------------------------------------- *)
(*                METHODS OF Face                *)
(* --------------------------------------------- *)            
  
PROCEDURE InitFace(self : Face) : Face =
  BEGIN
    self.sb := NEW(SetOfBorders.T);
    RETURN self
  END InitFace;
  
PROCEDURE IsFaceEmpty(self: Face) : BOOLEAN =
  BEGIN
    RETURN self.sb.isEmpty()    
  END IsFaceEmpty;
  
PROCEDURE Genus(self: Face) : CARDINAL =
  BEGIN
    RETURN self.sb.size()    
  END Genus;
  
PROCEDURE BordersOf(self: Face) : SetOfBorders.T =   
  BEGIN
    RETURN self.sb
  END BordersOf;
  
PROCEDURE InsertBorder(self: Face; b: Border) =
  BEGIN
    EVAL self.sb.insert(b);
    b.face := self
  END InsertBorder;
  
PROCEDURE RemoveBorder(self: Face; b: Border) = 
  BEGIN
    EVAL self.sb.delete(b);
    b.face:=NIL
  END RemoveBorder;
  
PROCEDURE TransferBorder(self: Face; b: Border) = 
  BEGIN
    WITH f = b.faceOf() DO
      f.removeBorder(b);
      self.insertBorder(b);
    END
  END TransferBorder;

PROCEDURE MergeFaces(self: Face; f: Face) = 
  VAR sb: TMBorder.T;
      b : Border;
  BEGIN
    WITH it = f.bordersOf().iterate() DO
      WHILE it.next(sb) DO 
        b:=NARROW(sb,Border);
        f.removeBorder(b);
        self.insertBorder(b)
      END
    END
  END MergeFaces;

PROCEDURE WalkOnFace(f: Face; P: VisitProc; GetFaces: BOOLEAN:=TRUE; qftv: QueueOfFaces:=NIL) = 
  VAR sb : TMBorder.T;    (* the border's ancestor; used in set of borders *)
      b  : Border;
  BEGIN
    WITH it = f.bordersOf().iterate() DO
      WHILE it.next(sb) DO 
        b:=NARROW(sb,Border);
        WalkOnBorder(b,P,GetFaces,qftv)
      END;
    END
  END WalkOnFace;

(* --------------------------------------------- *)
(*                METHODS OF Map                 *)
(* --------------------------------------------- *)            
PROCEDURE InitMap(self: Map): Map = 
  BEGIN
    self.f := NEW(Face).init();
    self.c := NIL;
    self.NC:=0;
    self.NB:=0;
    self.NF:=1;
    RETURN self;
  END InitMap;

PROCEDURE GetTCounter(self: Map) : TCounter = 
  VAR cnt : TCounter;
  BEGIN
    cnt.NC:=self.NC;
    cnt.NB:=self.NB;
    cnt.NF:=self.NF;
    RETURN cnt
  END GetTCounter;

PROCEDURE SetTCounter(self: Map; cnt: TCounter) = 
  BEGIN
    self.NC:=cnt.NC;
    self.NB:=cnt.NB;
    self.NF:=cnt.NF;
  END SetTCounter;

PROCEDURE RefFace(self: Map) : Face = 
  BEGIN
    RETURN self.f
  END RefFace;

PROCEDURE SetRefFace(self: Map; f: Face) = 
  BEGIN
    self.f := f;
  END SetRefFace;

PROCEDURE RefCorner(self: Map) : Corner = 
  BEGIN
    RETURN self.c
  END RefCorner;

PROCEDURE SetRefCorner(self: Map; c: Corner) = 
  BEGIN
    self.c := c;
    IF c # NIL THEN (* "c=NIL" is used to clear the Reference Corner *)
      self.f := c.left();
    END
  END SetRefCorner;

PROCEDURE WalkOnMap(m: Map; P: VisitProc) = 
  VAR qftv := NEW(QueueOfFaces);      (* faces tovisited *)
      f  : Face; 
      
  PROCEDURE FUnmark(rf: REFANY) = 
    BEGIN
      WITH f=NARROW(rf,Face) DO 
        f.unmark()
      END
    END FUnmark;
  
  BEGIN
    TRY 
      f:=m.f;
      QInit(qftv);
      QInsert(f,qftv);
      REPEAT 
        f:=QRemove(qftv);
        WalkOnFace(f,P,TRUE,qftv);
      UNTIL QIsEmpty(qftv);
    FINALLY
      QRelease(qftv,FUnmark)
    END;
  END WalkOnMap;

(* ===================================================== *)
(*     Auxiliar routines used in ReadTop and WriteTop    *)
(* ===================================================== *)
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 ReadTop(self: Map; rd: FileRd.T; vStack: REF ARRAY OF Vertex; 
                                           eStack: REF ARRAY OF Edge) = 
  CONST dig = SET OF CHAR{'0'..'9'};
  TYPE 
    elemcorner = RECORD 
      vnum : INTEGER;   (* number of the vertex in the corner           *)
      enum : INTEGER;   (* number of the edge in the corner             *)
      fwd  : Sign;       (* direction of the edge                        *)
      bnum : INTEGER;   (* number of the borders of the corner          *)
      ONnum : INTEGER;  (* number of the corner corresponding to ONext  *)
      BNnum : INTEGER;  (* number of the corner corresponding to LNext  *)
      ptr   : Corner;    (* reference to the corner to be created        *)
      exists: BOOLEAN:=FALSE (* TRUE=> that corner exists                *)
    END;
    elemborder = RECORD 
      face: INTEGER;
      desc: INTEGER;
      ptr : Border;
    END;
   
  VAR stackin : RECORD 
        corners  : REF ARRAY OF elemcorner;
        borders  : REF ARRAY OF elemborder;
      END;
      RefElem : RECORD 
        fnum : INTEGER;   (* number of the reference face *) 
        cnum : INTEGER;   (* number of the reference corners; 0 => doesn't exist *)
      END;
      
  PROCEDURE ReadCorners() =
    VAR vn, en: INTEGER;
    BEGIN
      FileFmt.ReadHeader(rd,"Corners Data","");
      EVAL FileFmt.ReadComment(rd,'#');
      FGet.Skip(rd);
      WHILE Rd.GetChar(rd) IN dig DO 
        Rd.UnGetChar(rd);
        WITH cnum=FGet.Int(rd) DO
          IF Extras.ReadNum(rd,vn) THEN stackin.corners[cnum].vnum:=vn
          ELSE stackin.corners[cnum].vnum:=0 END;
          IF Extras.ReadNum(rd,en) THEN stackin.corners[cnum].enum:=en 
          ELSE stackin.corners[cnum].enum:=0 END;
          stackin.corners[cnum].fwd:=FGet.Int(rd);
          stackin.corners[cnum].bnum:=FGet.Int(rd);
          stackin.corners[cnum].ONnum:=FGet.Int(rd);
          stackin.corners[cnum].BNnum:=FGet.Int(rd);
          stackin.corners[cnum].exists:=TRUE;
        END;
        FGet.EOL(rd);
        FGet.Skip(rd)
      END;
      Rd.UnGetChar(rd);
      FileFmt.ReadFooter(rd,"Corners Data"); 
    END ReadCorners;
  
  PROCEDURE ReadBorders() = 
    BEGIN
      FileFmt.ReadHeader(rd,"Borders Data","");
      EVAL FileFmt.ReadComment(rd,'#');
      FGet.Skip(rd);
      WHILE Rd.GetChar(rd) IN dig DO 
        Rd.UnGetChar(rd);
        WITH bnum = FGet.Int(rd) DO 
          stackin.borders[bnum].face:=FGet.Int(rd);
          stackin.borders[bnum].desc:=FGet.Int(rd);
        END;
        FGet.EOL(rd);
        FGet.Skip(rd)
      END;
      Rd.UnGetChar(rd);
      FileFmt.ReadFooter(rd,"Borders Data")
    END ReadBorders;

  PROCEDURE ReadFaces() = 
    BEGIN
      FileFmt.ReadHeader(rd,"Faces Data","");
      EVAL FileFmt.ReadComment(rd,'#');

      FGet.Skip(rd);
      WHILE Rd.GetChar(rd) IN dig DO 
        Rd.UnGetChar(rd);
        WITH 
          f = NEW(Face).init(),
          fnum = FGet.Int(rd),
          st = FGet.Int(rd)
        DO 

          (* --- updates the reference face --- *)
          IF fnum = RefElem.fnum THEN 
          (* this is the reference face *)
            self.f := f
          END;

          f.setNum(fnum);
          f.setStyle(st);

          FGet.Skip(rd);
          FGet.Match(rd,"-->");

          LOOP 
            WITH ch = Rd.GetChar(rd) DO
              IF ch = '\n' THEN 
                EXIT 
              ELSE
                IF ch # ',' THEN Rd.UnGetChar(rd); END;
                WITH 
                  bnum=FGet.Int(rd),
                  b = stackin.borders[bnum].ptr
                DO 
                  b.insertInFace(f)     
                END
              END;
            END;
          END;
        END;
        FGet.Skip(rd)
      END;
      Rd.UnGetChar(rd);
      FileFmt.ReadFooter(rd,"Faces Data");
    END ReadFaces;
      
  BEGIN
    (* --- initializes stack in --- *)
    stackin.corners  := NEW(REF ARRAY OF elemcorner,self.NC+1);
    stackin.borders  := NEW(REF ARRAY OF elemborder,self.NB+1);
    
    (* --- reads the number of the referece face and corner  --- *) 
    EVAL FileFmt.ReadComment(rd,'#');  (* ---  discards the blank line --- *)
    RefElem.fnum := NGet.Int(rd,"Reference Face");  FGet.EOL(rd);
    RefElem.cnum := NGet.Int(rd,"Reference Corner");  FGet.EOL(rd);
    EVAL FileFmt.ReadComment(rd,'#');  (* ---  discards the blank line --- *)
    (* --- reads input file and stores it in stackin --- *)
    ReadCorners();
    ReadBorders();

    (* --- creates the corners --- *)
    FOR i:=0 TO self.NC DO 
      IF stackin.corners[i].exists THEN 
        WITH 
          nc = NEW(Corner),
          vn = stackin.corners[i].vnum,
          en = stackin.corners[i].enum
        DO
          stackin.corners[i].ptr:=nc; 

          (* --- allocates space to corner's features  --- *)
          IF vn # 0 THEN 
            IF vStack[vn] = NIL THEN 
              vStack[vn]:=NEW(Vertex);
              vStack[vn].setNum(vn)
            END;
            nc.setVertex(vStack[vn]);
          END;
          IF en # 0 THEN 
            IF eStack[en] = NIL THEN 
              eStack[en]:=NEW(Edge);
              eStack[en].setNum(en);
            END;
            nc.initHalfEdge();
            nc.setHalfEdge(eStack[en],stackin.corners[i].fwd);
          END;


          nc.setNum(i);
        END
      END;
    END;
    (* --- creates the borders, updating their corner descriptor --- *)
    FOR i:=0 TO self.NB DO 
      WITH cnum = stackin.borders[i].desc DO 
        IF stackin.corners[cnum].exists THEN 
          WITH nb = NEW(Border).init(stackin.corners[cnum].ptr) DO 
            stackin.borders[i].ptr := nb;
            nb.setNum(i)
          END
        END;
      END
    END;

    (* --- sets the topology of the corners --- *)
    FOR i:=0 TO self.NC DO 
      IF stackin.corners[i].exists THEN 
        WITH 
          c = stackin.corners[i].ptr, 
          b = stackin.borders[stackin.corners[i].bnum].ptr   
        DO 
          c.setONext(stackin.corners[stackin.corners[i].ONnum].ptr);
          c.setLNext(stackin.corners[stackin.corners[i].BNnum].ptr);
          b.insertCorner(c)
        END;
      END
    END;

    
    (* --- reads the faces --- *)
    ReadFaces();
    
    FileFmt.ReadFooter(rd,"Topology"); 

    (* --- updates the pointer of the reference corner of the map --- *)
    IF RefElem.cnum # 0  THEN 
      self.c := stackin.corners[RefElem.cnum].ptr
    ELSE 
      self.c := NIL
    END;
  END ReadTop;

PROCEDURE WriteTop(self: Map; wr: FileWr.T; vStack: REF ARRAY OF Vertex; 
                                            eStack: REF ARRAY OF Edge) = 
  CONST 
    HeaderCorner = "number, vertex, edge,    fwd,  border, ONext,   LNext";
    HeaderBorder = "number,   face,      descriptor";
    HeaderFace   = "number,   style,     list of borders";
  
  VAR cWidth : CARDINAL := NumDigits(self.NC);
      bWidth : CARDINAL := NumDigits(self.NB);
      fWidth : CARDINAL := NumDigits(self.NF);
    
      stackout : RECORD 
        corners  : REF ARRAY OF Corner;
        borders  : REF ARRAY OF Corner; (* descriptors of the borders *)
        faces    : REF ARRAY OF Face;
      END;
      aux : BOOLEAN;

  PROCEDURE WriteCorner(c: Corner) = 
    BEGIN
      WITH
        cnum = c.getNum(),
        b    = c.borderOf(),
        bnum = b.getNum(),
        f    = b.faceOf(),
        fnum = f.getNum(),
        ONnum= c.oNext().getNum(),
        BNnum= c.lNext().getNum()
      DO
        Wr.PutText(wr, "    "&Fmt.Pad(Fmt.Int(cnum), cWidth)&"      ");
        IF stackout.corners[cnum] = NIL THEN stackout.corners[cnum]:=c END;

        IF NOT c.isOval() THEN 
          WITH vnum = c.org().getNum() DO 
            Wr.PutText(wr,"  "&Fmt.Pad(Fmt.Int(vnum), cWidth)&"      "); 
            IF vStack[vnum] = NIL THEN vStack[vnum]:=c.org() END;
          END
        ELSE 
          Wr.PutText(wr,"  "&Fmt.Pad("-", cWidth)&"      ");
        END;
        
        IF NOT c.isIsolatedVertex() THEN 
          WITH enum = c.halfEdge().edge().getNum() DO
            Wr.PutText(wr, Fmt.Pad(Fmt.Int(enum), cWidth)&"      "); 
            Wr.PutText(wr, Fmt.Pad(Fmt.Int(c.halfEdge().fwd()),  2)&"      ");
            IF eStack[enum] = NIL THEN eStack[enum]:=c.halfEdge().edge() END;
          END
        ELSE 
          Wr.PutText(wr, Fmt.Pad("-", cWidth)&"      "); 
          Wr.PutText(wr, Fmt.Pad("0",  2)&"      ");
        END;
        Wr.PutText(wr, Fmt.Pad(Fmt.Int(bnum),  cWidth)&"       ");
        Wr.PutText(wr, Fmt.Pad(Fmt.Int(ONnum), cWidth)&"       ");
        Wr.PutText(wr, Fmt.Pad(Fmt.Int(BNnum), cWidth));
        FPut.EOL(wr);
        IF stackout.borders[bnum] = NIL THEN 
           stackout.borders[bnum]:=b.borderDesc() 
        END;
        IF stackout.faces[fnum] = NIL THEN stackout.faces[fnum]:=f END;
      END;
    END WriteCorner;

  PROCEDURE WriteBorders() =
    BEGIN 
      FileFmt.WriteHeader(wr,"Borders Data","");
      FileFmt.WriteComment(wr,HeaderBorder,'#');
      FOR i:=0 TO self.NB DO 
        WITH d = stackout.borders[i] DO  
          IF d # NIL THEN 
            Wr.PutText(wr,"    "&Fmt.Pad(Fmt.Int(i),bWidth)&"     ");
            Wr.PutText(wr,"    "&Fmt.Pad(Fmt.Int(d.left().getNum()),fWidth)&"        ");
            Wr.PutText(wr,"    "&Fmt.Pad(Fmt.Int(d.getNum()),cWidth));
            FPut.EOL(wr)
          END
        END;
      END;
      FileFmt.WriteFooter(wr,"Borders Data"); 
    END WriteBorders;

  PROCEDURE WriteFaces() = 
    VAR b: Border;
        bt : TMBorder.T;
    BEGIN 
      FileFmt.WriteHeader(wr,"Faces Data","");
      FileFmt.WriteComment(wr,HeaderFace,'#');
      FOR i:=0 TO self.NF DO 
        aux:=FALSE;
        WITH f = stackout.faces[i]  DO  
          IF f # NIL THEN 
            WITH it = f.sb.iterate() DO 
              Wr.PutText(wr,"    "&Fmt.Pad(Fmt.Int(i),fWidth)&"     ");
              Wr.PutText(wr,"    "&Fmt.Int(f.getStyle()));
              Wr.PutText(wr,"    -->  ");
              WHILE it.next(bt) DO
                b:=NARROW(bt,Border);
                IF aux THEN Wr.PutText(wr,",  ")
                ELSE aux:=TRUE END;
                Wr.PutText(wr,Fmt.Pad(Fmt.Int(b.getNum()),bWidth));
              END;
              FPut.EOL(wr)
            END
          END
        END;
      END;
      FileFmt.WriteFooter(wr,"Faces Data"); 
    END WriteFaces;

  
  BEGIN
    FileFmt.WriteComment(wr," ",'#');  (* ---  writes a blank line --- *)
    FileFmt.WriteHeader(wr,"Topology","");  
    FileFmt.WriteComment(wr," ",'#');  (* ---  writes a blank line --- *)
    NPut.Int(wr,"Reference Face  ",self.f.getNum());  FPut.EOL(wr);
    WITH rc = self.c DO 
      IF rc # NIL THEN NPut.Int(wr,"Reference Corner",rc.getNum());  
      ELSE NPut.Int(wr,"Reference Corner",0); END;
      FPut.EOL(wr);
    END;
    FileFmt.WriteComment(wr," ",'#');  (* ---  writes a blank line --- *)

    (* --- initializes the stacks used during the writing process --- *)
    stackout.corners  := NEW(REF ARRAY OF Corner,self.NC+1);
    stackout.borders  := NEW(REF ARRAY OF Corner,self.NB+1);
    stackout.faces    := NEW(REF ARRAY OF Face,self.NF+1);

    FileFmt.WriteHeader(wr,"Corners Data","");  
    FileFmt.WriteComment(wr,HeaderCorner,'#');  
    
    (* --- writes corners and builds stack with vertices, edges and faces --- *)
    self.walkOn(WriteCorner);
    FileFmt.WriteFooter(wr,"Corners Data");  
    
    WriteBorders();
    WriteFaces();
    FileFmt.WriteFooter(wr,"Topology");  
  END WriteTop;


BEGIN
END TMC.