GENERIC IMPLEMENTATION MODULE DList;
PROCEDURE Init(VAR l : List);
BEGIN l.head := NIL; l.tail := NIL; l.count := 0 END Init;

PROCEDURE Append(VAR l : List; v : T);
VAR n : Node;
BEGIN
  NEW(n); n^.val := v; n^.next := NIL; n^.prev := l.tail;
  IF l.tail # NIL THEN l.tail^.next := n ELSE l.head := n END;
  l.tail := n; l.count := l.count + 1
END Append;

PROCEDURE Prepend(VAR l : List; v : T);
VAR n : Node;
BEGIN
  NEW(n); n^.val := v; n^.prev := NIL; n^.next := l.head;
  IF l.head # NIL THEN l.head^.prev := n ELSE l.tail := n END;
  l.head := n; l.count := l.count + 1
END Prepend;

PROCEDURE Count(VAR l : List) : INTEGER;
BEGIN RETURN l.count END Count;

PROCEDURE Get(VAR l : List; i : INTEGER) : T;
VAR n : Node; k : INTEGER;
BEGIN
  n := l.head; k := 0;
  WHILE k < i DO n := n^.next; k := k + 1 END;
  RETURN n^.val
END Get;

PROCEDURE Sum(VAR l : List) : T;
VAR n : Node; s : T;
BEGIN
  s := 0; n := l.head;
  WHILE n # NIL DO s := s + n^.val; n := n^.next END;
  RETURN s
END Sum;

PROCEDURE Reverse(VAR l : List);
VAR n, nx : Node;
BEGIN
  n := l.head;
  WHILE n # NIL DO
    nx := n^.next; n^.next := n^.prev; n^.prev := nx; n := nx
  END;
  n := l.head; l.head := l.tail; l.tail := n
END Reverse;

PROCEDURE ForEach(VAR l : List;
                  visit : PROCEDURE(VAR acc : INTEGER; v : T);
                  VAR acc : INTEGER);
VAR n : Node;
BEGIN
  n := l.head;
  WHILE n # NIL DO visit(acc, n^.val); n := n^.next END
END ForEach;
END DList.