\begin{sloppypar}
\raggedright\obeylines\setlength{\parindent}{0in}\setlength{\parskip}{0in}\setlength{\topsep}{0in}
si=sequence[int]
\hspace*{1pc}

putint = {\bf proc} (i:int)
\hspace*{0.4in} \% effects: outputs the integer i followed by a space to the primary
\hspace*{0.4in} \% output stream
\hspace*{1pc}

\hspace*{0.4in} stdout:stream := stream\$primary\_output()
\hspace*{1pc}

\hspace*{0.4in} stream\$puts(stdout,int\$unparse(i))
\hspace*{0.4in} stream\$putc(stdout,' ')
\hspace*{0.4in} {\bf end} putint
\hspace*{1pc}

putstr = {\bf proc} (s:string)
\hspace*{0.4in} \% effects: outputs the string s followed by a newline to the primary
\hspace*{0.4in} \% output stream
\hspace*{1pc}

\hspace*{0.4in} stdout:stream := stream\$primary\_output()
\hspace*{1pc}

\hspace*{0.4in} stream\$putl(stdout,s)
\hspace*{0.4in} {\bf end} putstr
\hspace*{1pc}

putnl = {\bf proc} ()
\hspace*{0.4in} \% effects: outputs a newline to the primary output stream
\hspace*{1pc}

\hspace*{0.4in} stdout:stream := stream\$primary\_output()
\hspace*{1pc}

\hspace*{0.4in} stream\$putc(stdout,'$\backslash$n')
\hspace*{0.4in} {\bf end} putnl
\hspace*{1pc}

breadth\_first\_tree = {\bf proc} (t: tree, n:int)
\hspace*{0.4in} \% effects: prints breadth-first list of t starting at node n.
\hspace*{0.4in} \% Each successive level of nodes is printed on a separate line
\hspace*{1pc}

\hspace*{0.4in} thisline:queue := queue\$create()\hspace*{0.4in} \% initalize by creating thisline
\hspace*{0.4in} queue\$enq(thisline,n)\hspace*{1.5in} \% and enqueuing the index of the top
\hspace*{4.0in} \% of the tree
\hspace*{1pc}

\hspace*{0.4in} {\bf while} \~{ }queue\$is\_empty(thisline) {\bf do}
\hspace*{0.8in} lastline:queue := thisline
\hspace*{0.8in} thisline := queue\$create()
\hspace*{0.8in} {\bf while} \~{ }queue\$is\_empty(lastline) {\bf do}
\hspace*{1.2in} i:int := queue\$deq(lastline)
\hspace*{1.2in} children:si := tree\$children(t,i)
\hspace*{1pc}

\hspace*{1.2in} putint(i)
\hspace*{1.2in} {\bf for} j:int {\bf in} si\$elements(children) {\bf do}
\hspace*{1.6in} queue\$enq(thisline,j)
\hspace*{1.6in} {\bf end}
\hspace*{1.2in} {\bf end}
\hspace*{0.8in} putnl()
\hspace*{0.8in} {\bf end}
\hspace*{0.4in} {\bf end} breadth\_first\_tree
\hspace*{1pc}

\%
\% test trees for the debugger
\%
\hspace*{1pc}

start\_up = {\bf proc} ()
\hspace*{0.4in} \% effects: tests breadth\_first\_tree with four different cases
\hspace*{1pc}

\hspace*{0.4in} putstr(``Testing test\_tree\_1'')
\hspace*{0.4in} breadth\_first\_tree(test\_tree\_1(),1)
\hspace*{0.4in} putnl()
\hspace*{1pc}

\hspace*{0.4in} putstr(``Testing test\_tree\_2'')
\hspace*{0.4in} breadth\_first\_tree(test\_tree\_2(),1)
\hspace*{0.4in} putnl()
\hspace*{1pc}

\hspace*{0.4in} putstr(``Testing test\_tree\_3'')
\hspace*{0.4in} breadth\_first\_tree(test\_tree\_3(),1)
\hspace*{0.4in} putnl()
\hspace*{1pc}

\hspace*{0.4in} t:tree,n:int := test\_tree\_4()
\hspace*{0.4in} putstr(``Testing test\_tree\_4 from the top'')
\hspace*{0.4in} breadth\_first\_tree(t,1)
\hspace*{0.4in} putnl()
\hspace*{0.4in} putstr(``Testing test\_tree\_4 from the middle'')
\hspace*{0.4in} breadth\_first\_tree(t,n)
\hspace*{0.4in} putnl()
\hspace*{1pc}

\hspace*{0.4in} {\bf end} start\_up
\hspace*{1pc}

test\_tree\_1 = {\bf proc} () {\bf returns} (tree)
\hspace*{0.4in} \% effects: returns a tree with 1 node
\hspace*{1pc}

\hspace*{0.4in} t:tree := tree\$create()
\hspace*{1pc}

\hspace*{0.4in} {\bf return}(t)
\hspace*{0.4in} {\bf end} test\_tree\_1
\hspace*{1pc}

test\_tree\_2 = {\bf proc} () {\bf returns} (tree)
\hspace*{0.4in} \% effects: returns a simple binary tree
\hspace*{1pc}

\hspace*{0.4in} t:tree := tree\$create()
\hspace*{0.4in} n1,n2,i:int
\hspace*{1pc}

\hspace*{0.4in} t, n1 := tree\$add\_node\_and\_edge(t,1)
\hspace*{0.4in} t, n2 := tree\$add\_node\_and\_edge(t,1)
\hspace*{1pc}

\hspace*{0.4in} t, i := tree\$add\_node\_and\_edge(t,n1)
\hspace*{0.4in} t, i := tree\$add\_node\_and\_edge(t,n1)
\hspace*{1pc}

\hspace*{0.4in} t, i := tree\$add\_node\_and\_edge(t,n2)
\hspace*{0.4in} t, i := tree\$add\_node\_and\_edge(t,n2)
\hspace*{1pc}

\hspace*{0.4in} {\bf return}(t)
\hspace*{0.4in} {\bf end} test\_tree\_2
\hspace*{1pc}

test\_tree\_3 = {\bf proc} () {\bf returns} (tree)
\hspace*{0.4in} \% effects: returns a tree with nodes having only one child each
\hspace*{1pc}

\hspace*{0.4in} t:tree := tree\$create()
\hspace*{0.4in} child:int
\hspace*{1pc}

\hspace*{0.4in} t,child := tree\$add\_node\_and\_edge(t,1)
\hspace*{0.4in} t,child := tree\$add\_node\_and\_edge(t,child)
\hspace*{0.4in} t,child := tree\$add\_node\_and\_edge(t,child)
\hspace*{0.4in} t,child := tree\$add\_node\_and\_edge(t,child)
\hspace*{0.4in} t,child := tree\$add\_node\_and\_edge(t,child)
\hspace*{1pc}

\hspace*{0.4in} {\bf return}(t)
\hspace*{0.4in} {\bf end} test\_tree\_3
\hspace*{1pc}

test\_tree\_4 = {\bf proc} () {\bf returns} (tree, int)
\hspace*{0.4in} \% effects: returns a reasonably complex tree and the label of
\hspace*{0.4in} \% a node for testing
\hspace*{1pc}

\hspace*{0.4in} t:tree := tree\$create()
\hspace*{0.4in} n1,n2,n3,n4,i:int
\hspace*{1pc}

\hspace*{0.4in} t, n1 := tree\$add\_node\_and\_edge(t,1)
\hspace*{0.4in} t, n2 := tree\$add\_node\_and\_edge(t,1)
\hspace*{0.4in} t, n3 := tree\$add\_node\_and\_edge(t,1)
\hspace*{1pc}

\hspace*{0.4in} t, i := tree\$add\_node\_and\_edge(t,n1)
\hspace*{0.4in} t, i := tree\$add\_node\_and\_edge(t,i)
\hspace*{0.4in} t, i := tree\$add\_node\_and\_edge(t,i)
\hspace*{1pc}

\hspace*{0.4in} t, i := tree\$add\_node\_and\_edge(t,n2)
\hspace*{0.4in} t, i := tree\$add\_node\_and\_edge(t,n2)
\hspace*{1pc}

\hspace*{0.4in} t, n4 := tree\$add\_node\_and\_edge(t,n3)
\hspace*{1pc}

\hspace*{0.4in} t, i := tree\$add\_node\_and\_edge(t,n4)
\hspace*{0.4in} t, i := tree\$add\_node\_and\_edge(t,n4)
\hspace*{1pc}

\hspace*{0.4in} {\bf return}(t,n4)
\hspace*{0.4in} {\bf end} test\_tree\_4
\end{sloppypar}
