(* GDDRAWING *)

PROCEDURE EdgeEndPoint(e: Edge; dirX, dirY: INT; READONLY pos: Points): Node;
  (*
    Returns the endpoint of "e" in the direction specified by "dirX" and "dirY".
    Chooses the end with larger X if "dirX > 0", the end with smaller X if "dirX < 0",
    and ignores the X coordinate if "dirX = 0".   The "dirY" parameter has the same
    meaning for the Y coordinate. The priority of the two axes is determined
    by the absolute values of "dirX" and "dirY".  In case of tie, returns the 
    lowest-numbered endpoint. *)


(* GDGEOMETRY *)

PROCEDURE FindFreeX(xBar: LONG; READONLY pt: Points): INT;
  (*
    Returns the abscissa nearest to "xBar" that is distinct from 
    the abscissas of all points in "pt".  If there are two such
    abscissas, returns the one closer to 0.25. *)



PROCEDURE AddNode(
    x, y: INT;     (* Desired position *)
    og, ig: NAT;   (* Output and input degrees. *)
    VAR dr: T; 
    dir: [-1..+1];
  ): Node = 
  VAR changed: BOOL := FALSE;
  BEGIN
    <* ASSERT dir # 0 *>
    HardClearPosition(x, y, dir, dr.pos^, dr.D, changed);
    RETURN DoAddNode(x, y, dr);
  END AddNode;
  
PROCEDURE LazyAddNode(
    x, y: INT;     (* Desired position *)
    og, ig: NAT;   (* Output and input degrees. *)
    VAR dr: T; 
    dir: [-1..+1];
  ): Node = 
  BEGIN
    <* ASSERT dir # 0 *>
    WITH 
      u = GatherLayerNodes(y, dr.pos^)^,
      xBar = FLOAT(x,LONG) + 0.25d0*FLOAT(dir,LONG),
      xFree = FindFreeNodeX(xBar, y, u, dr.pos^)
    DO
      RETURN DoAddNode(xFree, y, dr);
    END
  END LazyAddNode;
  
PROCEDURE FindFreeNodeX(
    xBar: LONG;
    READONLY u: Nodes;
    READONLY pos: Points;
  ): INT =
  (*
    Finds the integer abscissa that is different from the 
    abscissas of all nodes in the list "u", and is closer
    to the value "xBar". *)
  VAR xBest: INT;
      xPrev: INT;
      kt: NAT := 0;
      dBest: LONG := LAST(LONG);  (* Distance of best free slot found so far *)
  BEGIN
    IF NUMBER(u) = 0 THEN RETURN ROUND(xBar) END;
    WITH
      n = NUMBER(u),
      xMin = pos[u[0]][0],
      xMax = pos[u[n-1]][0]
    DO
      IF xBar <= FLOAT(xMin, LONG) THEN
        RETURN xMin - 1
      ELSIF xBar >=  FLOAT(xMax, LONG) THEN
        RETURN xMax + 1
      ELSE
        FOR x := xMin-1 TO xMax+1 DO 
          WHILE kt < n AND pos[u[kt]][0]  x DO INC(kt) END;
          IF kt < n AND pos[u[kt]][0] = x THEN
            INC(kt);
            <* ASSERT kt >= n OR pos[u[kt]][0] > x *>
          ELSE
            WITH d = ABS(xBar - FLOAT(x, LONG)) DO
              IF d < dBest THEN dBest := d; xBest := x END
            END
          END
        END;
        RETURN xBest
      END
    END
  END FindFreeNodeX;

PROCEDURE DoAddNode(
    x, y: INT;     (* Node's position *)
    og, ig: NAT;   (* Output and input degrees. *)
    VAR dr: T; 
  ): Node =
  (*
    Adds a node at the specified position. The client must make sure that 
    the position is free. *)
  BEGIN
    WITH w = dr.D.addNode(ig,og) DO
      IF dr.pos = NIL THEN 
        dr.pos := NEW(REF Points, MAX(10, w+1))
      ELSIF w >= NUMBER(dr.pos^) THEN 
        WITH sz = MAX(2*NUMBER(dr.pos^), w+1) DO 
          WITH posN = NEW(REF Points, sz) DO 
            SUBARRAY(posN^, 0, nN) := dr.pos^; dr.pos := posN
          END
        END
      END;
      (* DebugNodeMoved(w, Point{0,0}, Point{x,y}); *)
      dr.pos[w] := Point{x,y};
      RETURN w
    END
  END DoAddNode;

PROCEDURE DeleteNode(s: Node; VAR dr: T) = 
  BEGIN
    !! dr.pos[u] := dr.pos[w];
        
    
    WITH nN = dr.D.nV DO
      <* ASSERT s < nN *>
      IF s < nN-1 THEN
        (* Renumber node "nN-1" to be node "s": *)
        dr.pos[s] := dr.pos[nN-1];
        dr.D.ov[s] := dr.D.ov[nN-1];
        dr.D.iv[s] := dr.D.iv[nN-1];
        WITH ovs = dr.D.ov[s]^ DO
          FOR oks := 0 TO LAST(ovs) DO 
            WITH u = ovs[oks], ivu = dr.D.iv[u]^, iku = FindVertex(nN-1,ivu) DO
              ivu[iku] := s
            END
          END
        END;
        WITH ivs = dr.D.iv[s]^ DO
          FOR iks := 0 TO LAST(ivs) DO 
            WITH u = ivs[iks], ovu = dr.D.ov[u]^, oku = FindVertex(nN-1,ovu) DO
              ovu[oku] := s
            END
          END
        END;
      END;
      (* Discard the last node *)
      DEC(dr.D.nV)
    END
  END DeleteNode;
  
PROCEDURE SortEdges(VAR ee: Edges; cmp: EdgeCompareProc);
 (* 
   Sorts "e" so that "cmp(e[i-1], e[i]) <= 0" for all "i". *)

PROCEDURE GatherLayerNodes(y: INT; READONLY pos: Points): REF Nodes = 
  VAR nL: NAT := 0;
  BEGIN
    FOR v := 0 TO LAST(pos) DO 
      IF pos[v][1] = y THEN INC(nL) END
    END;
    WITH wR = NEW(REF Nodes, nL), w = wR^ DO
      nL := 0;
      FOR v := 0 TO LAST(pos) DO
        IF pos[v][1] = y THEN 
          (* Bubble to right position: *)
          VAR j: NAT := nL;
          BEGIN 
            WHILE j > 0 AND pos[w[j-1]][0] > pos[v][0] DO
              w[j] := w[j-1]; DEC(j)
            END;
            w[j] := v; INC(nL)
          END
        END
      END;
      RETURN wR
    END;
  END GatherLayerNodes;
  
PROCEDURE FindPointInLayer(x: INT; READONLY w: Nodes; READONLY pos: Points): NAT =
  BEGIN
    FOR k := 0 TO LAST(w) DO
      IF pos[w[k]][0] = x THEN RETURN k END
    END;
    RETURN LAST(NAT)
  END FindPointInLayer;
  
PROCEDURE PickClearingDir(x: INT; rnd: Random.T): [-1..+1] =
  (*
    Picks a suitable direction for shifting nodes when inserting
    something at abscissa "x".  Assumes the drawing is more
    or less balanced around "x = 0". 
  *)
  BEGIN
    RETURN SGN(2*SGN(x) + 2*rnd.integer(0,1)-1)
  END PickClearingDir;

(* DRAWING OUTPUT *)

<* UNUSED *>
PROCEDURE DebugNodeMoved(n: Node; oldP, newP: Point) =
  BEGIN
    Wr.PutText(stderr, 
      Fmt.Pad(FI(n), 3) & ": " & 
      FPoint(oldP) & " -> " 
      & FPoint(newP) & "\n"
    );
  END DebugNodeMoved;
  
<*UNUSED*>
PROCEDURE FEdge(e: Edge): TEXT =
  BEGIN
    RETURN "(" & FI(e[0]) & "," & FI(e[1]) & ")"
  END FEdge;
  
<*UNUSED*>
PROCEDURE FSign(s: [-1..+1]): TEXT =
  BEGIN
    IF s > 0 THEN 
      RETURN "+"
    ELSIF s < 0 THEN
      RETURN "-"
    ELSE
      RETURN "0"
    END
  END FSign;
  
PROCEDURE FPoint(READONLY p: Point): TEXT = 
  BEGIN
    RETURN "(" & FI(p[0]) & "," & FI(p[1]) & ")"
  END FPoint;

PROCEDURE Read(rd: Rd.T): T =
  BEGIN 
  END Read;

 
        
        Moreover, the edges of a polyline must have consistent
        vertical directions --- i.e. all towards increasing layers, or
        all towards decreasing layers. Therefore, there are no closed
        polylines --- every directed path in "D" must eventually reach
        a vertex of "G".

; and any two vertices that are neighbors in "G"
        must always be on different layers

<* UNUSED *>
PROCEDURE ChooseFlipDir(
    u: Node;
    READONLY pos: Points;
    rnd: Random.T;
  ): [-1..+1] =
  (*
    Chooses a direction for pushing Node "u" 
    such that there is at least some neighbor in that direction.
  *)
  VAR nPos, nNeg: NAT := 0;
  BEGIN
    WITH yu = pos[u][1] DO
      FOR ku := 0 TO LAST(G.ov[u]^) DO
        WITH v = G.nbor(u,+1,ku), yv = pos[v][1] DO
          IF yv > yu THEN INC(nPos) ELSE INC(nNeg) END
        END
      END;
      FOR iku := 0 TO LAST(G.iv[u]^) DO
        WITH v = G.nbor(u,-1,iku), yv = pos[v][1] DO
          IF yv > yu THEN INC(nPos) ELSE INC(nNeg) END
        END
      END
    END;
    IF nPos = 0 AND nNeg = 0 THEN
      RETURN 2*rnd.integer(0,1) - 1
    ELSIF nPos = 0 THEN
      RETURN -1
    ELSIF nNeg = 0 THEN
      RETURN +1
    ELSE
      RETURN SGN(2*(rnd.integer(0,nNeg+nPos)-nNeg)+1)
    END
  END ChooseFlipDir;

(* Last edited on 2000-01-09 01:04:07 by stolfi *)