placed: REF BOOLS;  (* (READONLY) Placed/unplaced flag. *)


        At any time, each node of "D" may be either `placed' or
        `unplaced'. There can be at most one placed node at each grid
        point, but any number of unplaced ones. (Think of placed nodes
        as attached to the paper, and unplaced ones as floating at
        some distance above it.) A grid position "(x,y)" is `free' if
        there is no *placed* node with those coordinates.

        All nodes with the same "y" coordinate, placed or unplaced,
        are called a `layer' of the graph. 
        
      layerNodes(y: INT): REF Nodes;
        (*
          Returns a list of all the nodes in layer "y", placed or 
          unplaced, sorted by abscissa. *)
      
      nodeRunAt(x, y: INT): REF Nodes;
        (*
          Returns the maximal list of consecutive placed 
          nodes in layer "y" that spans position "(x,y)";
          or an empty list if that position is free. *)
        
      placeNodes(READONLY u: Nodes; READONLY pos: Points);
      unplaceNodes(READONLY u: Nodes; READONLY pos: Points);
        (*
          Moves simultaneously node "u[i]" to position "pos[i]",
          making it placed or unplaced, respectively.
          client must make sure that no two placed nodes end up at 
          the same position, and that all edges incident to those nodes
          will still be spanning adjacent layers after the move. *)

PROCEDURE InitMethod(dr: T; G: GDGraph.T; allocJoints: NAT := 20): T =
        placedR =  NEW(REF BOOLS, allocNodes), 
        placed = SUBARRAY(placedR^, 0, nBaseV),
            
            ;
            placed[u] := FALSE

        dr.placed := placedR;

PROCEDURE CopyMethod(dr: T): T =
      placed = SUBARRAY(dr.placed^,0,nV),
      cp.placed := NEW(REF BOOLS, allocNodes); 
      SUBARRAY(cp.placed^,0,nV) := placed;

PROCEDURE NodeAtMethod(dr: T; x, y: INT): Node =
  VAR u: Node; lo, hi: NAT;
  BEGIN
    WITH layer = GetLayer(dr, y), n = layer.n DO
      IF n = 0 THEN 
        RETURN NoNode
      ELSE
        WITH
          w = SUBARRAY(layer.node^, 0, n),
          pos = SUBARRAY(dr.pos^, 0, dr.D.nV),,
          placed = SUBARRAY(dr.placed^, 0, dr.D.nV)
        DO
          GetNodesAtX(x, w, pos, lo, hi);
          IF lo > hi THEN
            RETURN NoNode
          ELSE
            (* See if there are any placed vertices in that set: *)
            u := NoNode;
            FOR k := lo TO hi DO 
              IF placed[k] THEN <* ASSERT u = NoNode *> u := w[k] END
            END;
            RETURN u
          END
        END
      END
    END
  END NodeAtMethod;

PROCEDURE NodeRunAtMethod(dr: T; x, y: INT): REF Nodes =
  VAR m: NAT; lo, hi: NAT;
  BEGIN
    WITH layer = GetLayer(dr, y), n = layer.n DO
      IF n = 0 THEN 
        RETURN NEW(REF Nodes, 0)
      ELSE
        WITH
          w = SUBARRAY(layer.node^, 0, n),
          pos = SUBARRAY(dr.pos^, 0, dr.D.nV),
          placed = SUBARRAY(dr.placed^, 0, dr.D.nV)
        DO
          GetNodesAtX(x, w, pos, lo, hi);
          IF lo > hi THEN
            RETURN NEW(Nodes, 0)
          ELSE
            (* Find start of run of consecutive placed vertices: *)
            m := 0;
            GetMaximalPlacedRun(w, lo, hi, m);
            (* Gather the packed vertices: *)
            WITH zR = NEW(REF Nodes, m), z = zR^ DO
              FOR i := 0 TO m-1 DO
                WHILE NOT packed[lo] DO INC(lo) END;
                z[i] := w[lo]
              END;
              RETURN zR
            END
          END
        END
      END
    END
  END NodeRunAtMethod;
  
PROCEDURE GetMaximalPlacedRun(
    READONLY w: Nodes; 
    VAR lo, hi: NAT; 
    VAR m: NAT;
    READONLY pos: Points;
  ) =
  (*
    Called with "lo = hi <= LAST(w)". Decreases "lo" and increases
    "hi" as much as possible, so that the *placed* nodes "w[k]" for
    "k" in the range "[lo..hi]" cover a set of consecutive abscissas.
    Also sets "m" to the count of those *placed* nodes. *)
     
  VAR xNext, xLim: INT;
  BEGIN
    (* Find start of run of consecutive placed vertices: *)
    xNext := pos[w[lo]][0];
    LOOP
      xLim := xNext;
      IF placed[lo] THEN DEC(xLim) END;
      IF lo = 0 THEN EXIT END;
      xNext := pos[w[lo-1]][0];
      IF xNext < xLim THEN EXIT END;
      DEC(lo);
    END;
    (* Find end of run, check for repeats, and count placed nodes: *)
    hi := lo; xNext := pos[w[hi]][0]; m := 0;
    LOOP
      xLim := xNext;
      IF placed[hi] THEN 
        INC(m); <* ASSERT xNext = xLim *> INC(xLim)
      END;
      IF hi = NUMBER(w) THEN EXIT END;
      xNext := pos[w[hi+1]][0];
      IF xNext > xLim THEN EXIT END;
      INC(hi);
    END;
  END GetMaximalPlacedRun;

(* Last edited on 2000-01-08 07:27:43 by stolfi *)