MODULE Topology;

IMPORT AlgGreedy, Graph;
IMPORT PktRouteIE;
IMPORT Rd, Text, Fmt, Thread, Sx, RefList, Word;

PROCEDURE FromName(nm: TEXT): Kind =
  BEGIN
    IF Text.Equal(nm, "grid") THEN RETURN Kind.Grid
    ELSIF Text.Equal(nm, "torus") THEN RETURN Kind.Torus
    ELSIF Text.Equal(nm, "butterfly") THEN RETURN Kind.Butterfly
    ELSIF Text.Equal(nm, "networkFromFile") THEN RETURN Kind.FromFile
    ELSE <* ASSERT FALSE *>
    END
  END FromName;

TYPE
  Grid = Graph.Sparse OBJECT
    w, h: CARDINAL;
  OVERRIDES
   nodeName := GridNodeName
  END;

PROCEDURE GridNodeName(g: Grid; id: CARDINAL): TEXT =
  VAR x := (id MOD g.w) + 1; y := (id DIV g.w) + 1; BEGIN
    RETURN Fmt.Int(y) & "," & Fmt.Int(x)
  END GridNodeName;

PROCEDURE NewGridBody(alg: AlgGreedy.T; w, h: CARDINAL): Graph.T
    RAISES {Thread.Alerted} =
  PROCEDURE NodeId(x, y: CARDINAL): CARDINAL =
    BEGIN RETURN x + y * w END NodeId;
  VAR g := NEW(Grid, w := w, h := h).init(sizeHint := h * w); BEGIN
    (* Add new nodes *)
    FOR j := 0 TO h - 1 DO
      FOR i := 0 TO w - 1 DO
        EVAL g.newNode();
        PktRouteIE.NewNode(alg, NodeId(i, j), FLOAT(i+2), FLOAT(j+2))
      END
    END;
    (* Add vertical edges *)
    FOR i := 0 TO w - 1 DO
      FOR j := 0 TO h - 2 DO
        VAR id1 := NodeId(i, j); id2 := NodeId(i, j+1); BEGIN
          g.newEdge(id1, id2);
          PktRouteIE.NewStraightEdge(alg, id1, id2)
        END
      END
    END;
    (* Add horizontal edges *)
    FOR i := 0 TO w - 2 DO
      FOR j := 0 TO h - 1 DO
        VAR id1 := NodeId(i, j); id2 := NodeId(i+1, j); BEGIN
          g.newEdge(id1, id2);
          PktRouteIE.NewStraightEdge(alg, id1, id2)
        END
      END
    END;
    (* Add grid labels *)
    FOR i := 1 TO w DO
      PktRouteIE.NewLabel(alg, Fmt.Int(i), FLOAT(i+1), 1.0)
    END;
    FOR j := 1 TO h DO
      PktRouteIE.NewLabel(alg, Fmt.Int(j), 1.0, FLOAT(j+1))
    END;
    RETURN g
  END NewGridBody;

PROCEDURE NewGrid(
    alg: AlgGreedy.T;
    w, h: CARDINAL;
    maxQueueSize: CARDINAL;
    bounded: BOOLEAN)
  : Graph.T
  RAISES {Thread.Alerted} =
  VAR res: Graph.T; BEGIN
    PktRouteIE.StartGraph(alg, w * h, maxQueueSize, bounded,
      FLOAT(w+2), FLOAT(h+2));
    res := NewGridBody(alg, w, h);
    PktRouteIE.EndGraph(alg);
    RETURN res
  END NewGrid;

PROCEDURE NewTorus(
    alg: AlgGreedy.T;
    w, h: CARDINAL;
    maxQueueSize: CARDINAL;
    bounded: BOOLEAN)
  : Graph.T
  RAISES {Thread.Alerted} =
  PROCEDURE NodeId(x, y: CARDINAL): CARDINAL =
    BEGIN RETURN x + y * w END NodeId;
  CONST Out = -1.0; Between = 0.5;
  VAR res: Graph.T; BEGIN
    PktRouteIE.StartGraph(alg, w * h, maxQueueSize, bounded,
      FLOAT(w+2), FLOAT(h+2));
    res := NewGridBody(alg, w, h);
    IF h > 1 THEN
      FOR i := 0 TO w - 1 DO
	VAR id1 := NodeId(i, 0); id2 := NodeId(i, h-1); BEGIN
	  res.newEdge(id1, id2);
	  PktRouteIE.NewCurvedEdge(alg, id1, id2,
	    FLOAT(i+2)+Between, 2.0-Out, FLOAT(i+2)+Between, FLOAT(h+1)+Out)
	END
      END
    END;
    IF w > 1 THEN
      FOR j := 0 TO h - 1 DO
	VAR id1 := NodeId(0, j); id2 := NodeId(w-1, j); BEGIN
	  res.newEdge(id1, id2);
	  PktRouteIE.NewCurvedEdge(alg, id1, id2,
	    2.0-Out, FLOAT(j+2)+Between, FLOAT(w+1)+Out, FLOAT(j+2)+Between)
	END
      END
    END;
    PktRouteIE.EndGraph(alg);
    RETURN res
  END NewTorus;

PROCEDURE NewButterfly(
    alg: AlgGreedy.T;
    dim: CARDINAL;
    maxQueueSize: CARDINAL;
    bounded: BOOLEAN)
  : Graph.T
  RAISES {Thread.Alerted} =
  PROCEDURE Exp(n: CARDINAL): CARDINAL =
    VAR res: CARDINAL := 1; BEGIN
      WHILE n > 0 DO res := res * 2; DEC(n) END;
      RETURN res
    END Exp;
  VAR
    w := dim + 1; h := Exp(dim); mask := h DIV 2;
    g := NEW(Grid, w := w, h := h).init(sizeHint := h * w);
  PROCEDURE NodeId(x, y: CARDINAL): CARDINAL =
    BEGIN RETURN x + y * w END NodeId;
  BEGIN
    PktRouteIE.StartGraph(alg, w * h, maxQueueSize, bounded,
      FLOAT(2*w), FLOAT(h+1));
    (* Add new nodes *)
    FOR j := 0 TO h - 1 DO
      FOR i := 0 TO w - 1 DO
        EVAL g.newNode();
        PktRouteIE.NewNode(alg, NodeId(i, j), FLOAT((2*i)+1), FLOAT(j+1))
      END
    END;
    (* Add edges *)
    FOR i := 0 TO w - 2 DO
      FOR j := 0 TO h - 1 DO
        VAR id1 := NodeId(i, j); id2a := NodeId(i+1, j); BEGIN
          g.newEdge(id1, id2a);
          PktRouteIE.NewStraightEdge(alg, id1, id2a);
          VAR id2b := NodeId(i+1, Word.Xor(j, mask)); BEGIN
            g.newEdge(id1, id2b);
            PktRouteIE.NewStraightEdge(alg, id1, id2b)
          END
        END
      END;
      mask := mask DIV 2
    END;
    PktRouteIE.EndGraph(alg);
    RETURN g
  END NewButterfly;

TYPE
  Coord = RECORD x, y: REAL END;
  Coords = REF ARRAY OF Coord;

PROCEDURE NewFromFile(
    alg: AlgGreedy.T;
    rd: Rd.T;
    maxQueueSize: CARDINAL;
    bounded: BOOLEAN)
  : Graph.T
  RAISES {BadGraph, Thread.Alerted} =
  VAR sx: Sx.T; curr: RefList.T; BEGIN
    TRY sx := Sx.Read(rd) EXCEPT
      Rd.EndOfFile => RAISE BadGraph("Unexpected end-of-file")
    | Sx.ReadError (msg) => RAISE BadGraph(msg)
    END;
    TYPECASE sx OF RefList.T (v) => curr := v ELSE
      RAISE BadGraph("File must be a list")
    END;
    VAR w, h: REAL; num: CARDINAL; g: Graph.Sparse; coords: Coords; BEGIN
      ReadCoord(curr.head, w, h); curr := curr.tail;
      num := RefList.Length(curr.head);
      g := NEW(Graph.Sparse).init(sizeHint := num);
      PktRouteIE.StartGraph(alg, num, maxQueueSize, bounded, w, h);
      coords := ReadNodes(alg, curr.head, g); curr := curr.tail;
      ReadEdges(alg, curr.head, g); curr := curr.tail;
      ReadLabels(alg, curr.head);
      IF curr.tail # NIL THEN
        RAISE BadGraph("Too many elements in top-level list")
      END;
      PktRouteIE.EndGraph(alg);
      RETURN g
    END
  END NewFromFile;

PROCEDURE ReadNodes(alg: AlgGreedy.T; l: RefList.T; g: Graph.Sparse): Coords
    RAISES {BadGraph, Thread.Alerted} =
  VAR id := 0; res: Coords;
  PROCEDURE ReadNode(node: RefList.T) RAISES {BadGraph, Thread.Alerted} =
    VAR x, y: REAL; BEGIN
      ReadCoord(node, x, y);
      res[id] := Coord{x := x, y := y};
      EVAL g.newNode();
      PktRouteIE.NewNode(alg, id, x, y)
    END ReadNode;
  BEGIN
    res := NEW(Coords, RefList.Length(l));
    WHILE l # NIL DO
      TYPECASE l.head OF RefList.T (r) => ReadNode(r) ELSE
        RAISE BadGraph("Bad node specification")
      END;
      INC(id);
      l := l.tail
    END;
    RETURN res
  END ReadNodes;

PROCEDURE ReadEdges(
    alg: AlgGreedy.T;
    l: RefList.T;
    g: Graph.Sparse)
    RAISES {BadGraph, Thread.Alerted} =
  PROCEDURE ReadEdge(edge: RefList.T) RAISES {BadGraph, Thread.Alerted} =
    VAR from, to: INTEGER; n := g.numNodes(); len:=RefList.Length(edge); BEGIN
      IF len # 2 AND len # 4 THEN
        RAISE BadGraph("Edge specification has wrong number of elements")
      END;
      TYPECASE edge.head OF REF INTEGER (i) => from := i^ ELSE
        RAISE BadGraph("Bad 'from' node in edge")
      END;
      edge := edge.tail;
      TYPECASE edge.head OF REF INTEGER (i) => to := i^ ELSE
        RAISE BadGraph("Bad 'to' node in edge")
      END;
      edge := edge.tail;
      IF NOT (0 <= from AND from < n AND 0 <= to AND to < n) THEN
        RAISE BadGraph("Bad node id in edge specification")
      END;
      g.newEdge(from, to);
      CASE len OF <* NOWARN *>
        2 => PktRouteIE.NewStraightEdge(alg, from, to)
      | 4 =>
          VAR x1, y1, x2, y2: REAL; BEGIN
            ReadCoord(edge.head, x1, y1); edge := edge.tail;
            ReadCoord(edge.head, x2, y2);
            PktRouteIE.NewCurvedEdge(alg, from, to, x1, y1, x2, y2)
          END
      END
    END ReadEdge;
  BEGIN
    WHILE l # NIL DO
      TYPECASE l.head OF RefList.T (r) => ReadEdge(r) ELSE
        RAISE BadGraph("Bad edge specification")
      END;
      l := l.tail
    END
  END ReadEdges;

PROCEDURE ReadLabels(alg: AlgGreedy.T; l: RefList.T)
    RAISES {BadGraph, Thread.Alerted} =
  PROCEDURE ReadLabel(label: RefList.T) RAISES {BadGraph, Thread.Alerted} =
    VAR txt: TEXT; x, y: REAL; BEGIN
      IF RefList.Length(label) # 3 THEN
        RAISE BadGraph("Label specification has wrong number of elements")
      END;
      TYPECASE label.head OF TEXT (t) => txt := t ELSE
        RAISE BadGraph("Bad label specification")
      END;
      label := label.tail;
      ReadCoord(label.head, x, y);
      PktRouteIE.NewLabel(alg, txt, x, y)
    END ReadLabel;
  BEGIN
    WHILE l # NIL DO
      TYPECASE l.head OF RefList.T (r) => ReadLabel(r) ELSE
        RAISE BadGraph("Bad label specification")
      END;
      l := l.tail
    END
  END ReadLabels;

PROCEDURE ReadCoord(l: RefList.T; VAR (*OUT*) x, y: REAL) RAISES {BadGraph} =

Requires l to be a list of 2 real numbers. Sets x and y to these two values; raises BadGraph otherwise.

  BEGIN
    TYPECASE l.head OF REF REAL (r) => x := r^ ELSE
      RAISE BadGraph("Bad x coordinate")
    END;
    l := l.tail;
    TYPECASE l.head OF REF REAL (r) => y := r^ ELSE
      RAISE BadGraph("Bad y coordinate")
    END;
    IF l.tail # NIL THEN
      RAISE BadGraph("Too many elements in coordinate pair")
    END
  END ReadCoord;

BEGIN
END Topology.