[comp.text.tex] style to include algorithms

sumit@cs.scarolina.edu (Sumit Chakravarty) (06/22/91)

Hi people,
	
	I'm looking for a style that will let me include algorithms in
my document -- one which will do things like put comments in a 
different font, boldface a set of keywords ( like if, while, end etc.)
and maybe take care of the tabbing involved.

	Anyone know of any such style?  Help would be much appreciated.
I'd love to try writing one, but time is short...

	Incidentally this is my first posting so please excuse any major
mess-ups.

Sumit
sumit@cs.scarolina.edu

rig@eng.umd.edu (Ronald Greenberg) (06/24/91)

(This message is about 265 lines long -- sorry.)

In article <sumit.677606720@oak.cs.scarolina.edu> sumit@cs.scarolina.edu (Sumit Chakravarty) writes:
>	I'm looking for a style that will let me include algorithms in
>my document -- one which will do things like put comments in a 
>different font, boldface a set of keywords ( like if, while, end etc.)
>and maybe take care of the tabbing involved.

I just define a bunch of macros for the keywords and comments, but I
do have some more involved stuff in order to get appropriate tabbing
and to get all the lines numbered sequentially and referenceable
(\ref).  Following is a file you could run through LaTeX to see an
example of the use of my program macros along with some commentary.

Disclaimers: This stuff is kludgy, and you may find a lot of clutter
here.  I've included some stuff to diddle captions, but I think that
is separable from the rest.

\documentstyle[12pt]{article}

\setlength{\topmargin}{-.53in}
\setlength{\oddsidemargin}{-.03in}
\setlength{\textwidth}{6.36in}
\setlength{\textheight}{9in}
\setlength{\parskip}{\medskipamount}

\begin{document}

%%%%%%%%%%%  CAPTIONS (These macros should be optional) %%%%%%%%%%%%

\makeatletter

\def\fnum@figure{{\bf Figure \thefigure}}
\def\fnum@table{{\bf Table \thetable}}

% For use in indenting captions
% Note for the centering of captions to work exactly right, there should
% be no space after the text of the caption.
\newlength{\captionwidth}

% Make captions be in footnote size and indented
\long\def\@caption#1[#2]#3{\par\addcontentsline{\csname
  ext@#1\endcsname}{#1}{\protect\numberline{\csname 
  the#1\endcsname}{\ignorespaces #2}}\begingroup
    \@parboxrestore
\setlength{\captionwidth}{\columnwidth}%
\addtolength{\captionwidth}{-2\leftmargini}%
\hspace*{\leftmargini}%
\parbox{\captionwidth}%
{\footnotesize
 \@makecaption{\csname fnum@#1\endcsname}{\ignorespaces #3}}%
\hspace*{\leftmargini}%
\par
\endgroup}

% Provide captions for figures occupying full page width when in twocolumn mode
% Note must use \dblcaption.
\def\dblcaption{\refstepcounter\@captype \@dblarg{\@dblcaption\@captype}}
\long\def\@dblcaption#1[#2]#3{\par\addcontentsline{\csname
  ext@#1\endcsname}{#1}{\protect\numberline{\csname 
  the#1\endcsname}{\ignorespaces #2}}\begingroup
    \@parboxrestore
\setlength{\captionwidth}{\textwidth}%
\addtolength{\captionwidth}{-2\leftmargini}%
\hspace*{\leftmargini}%
\parbox{\captionwidth}%
{\footnotesize
 \@makecaption{\csname fnum@#1\endcsname}{\ignorespaces #3}}%
\hspace*{\leftmargini}%
\par
\endgroup}

\makeatletter

%%%%%%%%%%%%%%%%%%% END OF MACROS FOR CAPTIONS %%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%% MACROS FOR PROGRAMS %%%%%%%%%%%%%%%%%%%%%%%

% The following environment is the type of object for which LaTeX will
% automatically determine width and therefore can center automatically.

\newenvironment{tabpackage}
{\begin{minipage}{\columnwidth}\begin{tabbing}}%
{\end{tabbing}\end{minipage}}

% General macros for programs and subprograms follow.

\newcounter{proglevel}
\newcounter{progline}
\newlength{\linenosep}
\newlength{\subprogindent}
\newlength{\progitemhangindent}
\newlength{\addprogitemsep}

\newenvironment{program}[1]%
{\setcounter{proglevel}{0}\setcounter{progline}{0}
 \settowidth{\linenosep}{\quad}
 \settowidth{\subprogindent}{\qquad}\settowidth{\progitemhangindent}{\quad}
 \setlength{\addprogitemsep}{0pt}
\newcommand{\setsubprogtabs}{#1\=\hspace*{\linenosep}
			     \hspace*{\value{proglevel}\subprogindent}\=
			     \hspace*{\progitemhangindent}\=\+\+\+\kill}
 \begin{tabpackage}\setlength{\tabbingsep}{0pt}\setsubprogtabs}%
{\end{tabpackage}}

% NOT TO BE USED AS AN ENVIRONMENT; USE ONLY \subprogram AND \endsubprogram
\newenvironment{subprogram}%
{\stepcounter{proglevel}\pushtabs\<\<\<\-\-\-\setsubprogtabs}%
{\poptabs\addtocounter{proglevel}{-1}}

\newif\ifprogitemarg
\makeatletter
\def\progitem{\@ifnextchar [{\progitemargtrue\progitemwarg}%
{\progitemargfalse\progitemwarg[\proglinenum]}}
\makeatother

\newlength{\progitemstrutheight}
\setlength{\progitemstrutheight}{0pt} % really start at {\baselineskip} ??
\addtolength{\progitemstrutheight}{\addprogitemsep}

\def\progitemwarg[#1]{\<\< #1 \'\>\rule{0pt}{\progitemstrutheight}%
\ifprogitemarg\else%
\addtocounter{progline}{-1}\refstepcounter{progline}\ignorespaces\fi}

\newcommand{\proglinenum}{\refstepcounter{progline}\theprogline}

\newcommand{\proglabel}[1]{\label{#1}\ignorespaces}

\newcommand{\progcom}[1]{\qquad $\langle${\sl #1}$\rangle$}

% Some additional macros convenient for use inside programs follow

\newcommand{\Begin}{{\bf begin\ }}
\newcommand{\End}{{\bf end\ }}
\newcommand{\Do}{{\bf do\ }}
\newcommand{\Od}{{\bf od}}
\newcommand{\Enddo}{{\bf enddo}}
\newcommand{\Loop}{{\bf loop\ }}
\newcommand{\Endloop}{{\bf endloop}}
\newcommand{\For}{{\bf for\ }}
\newcommand{\Endfor}{{\bf endfor}}
\newcommand{\Foreach}{{\bf foreach\ }}
\newcommand{\To}{{\bf to\ }}
\newcommand{\If}{{\bf if\ }}
\newcommand{\Then}{{\bf then\ }}
\newcommand{\Else}{{\bf else\ }}
\newcommand{\Elif}{{\bf elif\ }}
\newcommand{\Fi}{{\bf fi}}
\newcommand{\Endif}{{\bf endif}}
\newcommand{\While}{{\bf while\ }}
\newcommand{\Endwhile}{{\bf endwhile}}
\newcommand{\Repeat}{{\bf repeat\ }}
\newcommand{\Until}{{\bf until\ }}
\newcommand{\Break}{{\bf break}}
\newcommand{\Case}{{\bf case\ }}
\newcommand{\Of}{{\bf of\ }}
\newcommand{\Procedure}{{\bf procedure\ }}
\newcommand{\Return}{{\bf return\ }}
\newcommand{\Call}{{\bf call\ }}
\newcommand{\With}{{\bf with\ }}
\newcommand{\Imports}{{\bf imports\ }}
\newcommand{\Var}{{\bf var\ }}
\newcommand{\Type}{{\bf type\ }}
\newcommand{\Assert}{{\bf assert\ }}
\newcommand{\True}{{\rm true}}
\newcommand{\False}{{\rm false}}

%%%%%%%%%%%%%%%%%%% END OF MACROS FOR PROGRAMS %%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%% EXAMPLE PROGRAM CENTERED IN A FIGURE %%%%%%%%%%%%%%%%%%

%%% Macros just for the particular example here

\newcommand{\lambdaguess}{\lambda_{{\it guess}}}

\newcommand{\random}{{\it RANDOM}}
\newcommand{\tryguess}{\ifmmode \mbox{\it TRY-GUESS}
		       \else {\it TRY-GUESS}\fi}

\newcommand{\set}[1]{\left\{#1\right\}}

%%% The actual example program in figure:

\begin{figure}
\centering
\begin{program}{99}
\progitem[] Algorithm \random\\
\progitem \proglabel{line-SendMRandom}send $M$\\
\progitem $U \gets M-\set{\mbox{messages delivered}}$\\
\progitem $\lambdaguess \gets 2$\\
\progitem \While $k_1\lambdaguess < k_2\lg n$ and $U \not= \emptyset$ \Do\\
   \subprogram
   \progitem $\tryguess(\lambdaguess)$\\
   \progitem $\lambdaguess \gets \lambdaguess^2$\\
   \endsubprogram
\progitem \Endwhile\\
\progitem \proglabel{line-ShiftGearsRandom}
	  $\lambdaguess \gets (k_2/k_1)\lg n \lg\lg n$\\
\progitem \While $U \not= \emptyset$ \Do\\
   \subprogram
   \progitem \proglabel{line-SecondCallRandom} $\tryguess(\lambdaguess)$\\
   \progitem $\lambdaguess \gets 2\lambdaguess$\\
   \endsubprogram
\progitem \Endwhile
\end{program}
 \caption[The algorithm \random\/ for delivering a message set $M$]
 {The randomized algorithm \random\/ for delivering a message set $M$
on a fat-tree with $n$ processors.  This algorithm achieves the
running times in Figure~\ref{fig-RunningTimes} with high probability
if the constants $k_1$ and $k_2$ are appropriately chosen.  Since the
load factor $\lambda(M)$ is not known in advance, \random\/
makes guesses, each one being tried out by the subroutine \tryguess.}
 \label{fig-Random}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%% END OF EXAMPLE %%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% COMMENTS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Along with the program macros, I have included some macros that alter
the way that captions are set.  Specifically, a smaller typesize and
narrower margins are used.  Also Figure and Table labels at the
beginning of the caption are boldfaced.  If you don't like the
alterations, you should be able to chop out that part without ill
effect.  I have clearly marked the macros that are for fiddling with
the captions.

I'm not going to try to explain in words everything about how to use
the program macros.  You should first look at the example program in
this file to get the general idea.  (That is look at the LaTeX source
for the example.)

The argument to the program environment is supposed
to be at least as wide as the widest line label (number usually).

The use of \verb+\subprogram+ and \verb+\endsubprogram+ instead of
\verb+\begin{subprogram}+ and \verb+\end{subprogram}+ is due to some
subtlety in the LaTeX implementation of environments that made me get
errors when I went that way.  But that may have been an outdated
version of LaTeX.

I believe I set things up properly so that \verb+\progitem+ could take
an optional argument for the line label the way that \verb+\item+
does, otherwise you get sequential numbering throughout the program.

In order to make symbolic labels by which you could reference line
numbers, I needed a new version of \verb+\label+ called
\verb+\proglabel+.  It's argument and the \verb+\ref+'s to it are just
as for \verb+\label+ though.  I think the other requirement is that
the \verb+\proglabel+ should appear before the first \verb+\\+ in a
progitem.  (Yes a progitem can have multiple lines; the indentation of
successive lines is half as much as the indentation for going down to
the next subprogram level.  Line breaking in progitems must be
explicitly indicated with \verb+\\+.  In addition, each progitem must
end with \verb+\\+ except for the last one in the program
environment.)  In any case, the example shows that putting the
\verb+\proglabel+ at the beginning of the progitem is safe.  (I'll
just illustrate here that I can reference a line of the program, e.g.,
line~\ref{line-ShiftGearsRandom}.)

In the example here, I have included the program centered in a figure,
and you can see that I didn't need to figure out what the width of the
program would be.  That is because the program environment is
implemented as a tabbing environment inside of a minipage.

\end{document}
--

Ronald I. Greenberg	(Ron)		rig@eng.umd.edu