The alg package^{∗}

Staffan Ulfberg staffanu@nada.kth.se

20 June 1995

Abstract

This package defines two environments for typesetting algorithms in L^{A}TEX 2ε. Lines are automatically numbered and can be referenced, the means for easy indentation is provided, and algorithms can be made floating bodies if desired.

1 Introduction

algtab alg.sty defines two environments. The algtab environment is used to typeset

an algorithm with automatically numbered lines; it also takes care of indentation.

algorithm The algorithm environment can be used to encapsulate the algtab environment in a floating body together with a header, a caption, etc. The package recognizes a few language options and changes its fixed output strings accordingly. Please tell the author of this package if you need support for another language!

1.1 The algorithm environment

The algorithm environment starts a floating body; its placement is decided by an optional agrument that can be any combination of t, b, p, or h. By default, the placement H (Here!) is used, so the float does not float after all. See the description of the float package by Anselm Lingnau for more details about this. Inside the algorithm environment, the text will be indented from the left and right edges. It is possible to put a \caption within the float, and also to generate

\listofalgorithms a list of algorithms with the \listofalgorithms command.

Three other commands are defined for use in the algorithm environment:

\algname \algname takes two arguments of which the first is printed using small caps, followed by the second in parentheses.

\algdescript \algdescript takes one argument which is printed after the string “Description:” in boldface letters.

\alginout \alginout takes two arguments which are printed after the strings “Input:” and “Output:” respectively.

1.2 The algtab environment

In the algtab environment, an algorithm is typed line by line, separating lines by \\. Every time a new line is started, it will be numbered in the left margin starting at line 1. A single “line” of the algorithm can span several lines on the page, but a line number will only be printed after each \\ command. The current \ref value is also set, so that a label can be entered; it’s recommended that

\alglabel \alglabel is used for this purpose.

algtab* The algtab environment has a star-form variant that supresses line number generation; if the \alglabel macro is used in this case, the supplied label argument is printed as-is in the left margin of the algorithm (where the line numbers usually

\algref are printed). The macro \algref corresponds to \alglabel in the way that it prints either the referenced label’s value, or the label name literally if no line numbers are used. However, \algref can’t be used outside the algtab environment: use \ref intead. The algtab environment indents the algorithm to make room for the line numbers; the algtab* does not indent the algorithm by default. However, both environments take an optional argument specifying the amount of indentation that is desired.

\algbegin There are two important macros, \algbegin and \algend defined in the algtab

\algend environment. These macros start and stop additional indentation respectively; they should always be used at the beginning of a line. These macros are already included in some of the macros that are special to the algtab environment.

2 Example

This section shows how to typeset Algorithm 1 using the alg package in L^{A}TEX 2ε:

 \begin{algorithm}[h]
 \caption{Example of the \texttt{algorithm} environment.\label{alg:ex}}
 \alginout{An ordered set $U=\{u_1,u_2,\dots,u_n\}$.}
          {The set's maximum element, and a set $A$, $|A|=\log n$,
           containing the next largest element.  (If $n=1$, then
           $A=\emptyset$).}
 \algname{Max2}{$U$}
 \begin{algtab}
 \algif{$|U|=1$}
         \algreturn $(u_1, \emptyset)$ \\
 \algelsif{$|U|=2$}
         \algifthenelse{$u_1>u_2$}{\algreturn $(u_1, \{u_2\})$}
                                  {\algreturn $(u_2, \{u_1\})$}
 \algelse

∗This file was last revised 20 June 1995.

Algorithm 1: Example of the algorithm environment. Input: An ordered set U = {u_{1}, u_{2}, …, u_{n}}. Output: The set’s maximum element, and a set A, |A| = log n, containing the next largest element. (If n = 1, then A = ∅). Max2(U)

(1) if |U| = 1

(2) return (u_{1}, ∅)

(3) else if |U| = 2

(4) if u_{1} > u_{2} then return (u_{1}, {u_{2}})

(5) else return (u_{2}, {u_{1}})

(6) else

(7) (b, B) ← Max2({u_{i}}_{i=1}^{⌊n/2⌋})

(8) (c, C) ← Max2({u_{i}}_{i=⌊n/2⌋+1}^{n})

(9) if b > c then return (b, {c} ∪ B)

(10) else return (c, {b} ∪ C)

 $(b,B) \leftarrow$
    \algcall{Max2}{$\{u_i\}_{i=1}^{\lfloor n/2\rfloor}$}\\
 $(c,C) \leftarrow$
    \algcall{Max2}{$\{u_i\}_{i=\lfloor n/2\rfloor+1}^{n}$}\\
 \algifthenelse{$b>c$}{\algreturn $(b, \{c\}\cup B)$}
                      {\algreturn $(c, \{b\}\cup C)$}
\algend
\end{algtab}
\end{algorithm}

There is a list of all programming constructs available in the algtab environment at the end of this document. They work very much like the macros used above. As a general rule, if a macro doesn’t take an argument, a space charater is included at the end of the macro definition. For example, type $a=0$ \algor \algnot $b=0$ to produce “a = 0 or not b = 0.”

3 The Implementation

1 ⟨∗package⟩

The float package by Anselm Lingnau is used for floating algorithms.

2 \RequirePackage{float, ifthen}

Here are the varible declarations. \algmarginwidth, \alglinenowidth, and \algtabwidth define the amount of indentation of the entire algorithm, the space reserved for line numbers, and the indentation made by \algbegin respectively.

3 \newlength{\algmarginwidth}\setlength{\algmarginwidth}{.5in}
4 \newlength{\alglinenowidth}\setlength{\alglinenowidth}{1.2cm}
5 \newlength{\algtabwidth}\setlength{\algtabwidth}{.5cm}
6 \newlength{\alg@fromleft}

 7 \newlength{\alg@tmplen}
 8 \newsavebox{\alg@tmpbox}
 9 \newcounter{alg@inmargin}\setcounter{alg@inmargin}{0}
10 \newcounter{algline}
11 \newboolean{alg@linenums}

The strings used in captions and in the List of Algorithms differ in some languages.

12 \DeclareOption{english}{\def\alg@floatname{Algorithm}
13  \def\alg@listname{List of Algorithms}
14  \def\alg@descname{Description}
15  \def\alg@inputname{Input}
16  \def\alg@outputname{Output}}
17 \DeclareOption{american}{\def\alg@floatname{Algorithm}
18  \def\alg@listname{List of Algorithms}
19  \def\alg@descname{Description}
20  \def\alg@inputname{Input}
21  \def\alg@outputname{Output}}
22 \DeclareOption{swedish}{\def\alg@floatname{Algoritm}
23  \def\alg@listname{Algoritmer}
24  \def\alg@descname{Beskrivning}
25  \def\alg@inputname{Input}
26  \def\alg@outputname{Output}}
27 \ExecuteOptions{english}
28 \ProcessOptions

The following definitions set up the properties of the algorithmfloat.

29 \newcommand\floatc@alg[2]{{\bfseries\rmfamily
30 \hspace{\algmarginwidth}#1:} #2\par}
31 \newcommand\fs@alg{
32 \let\@fs@capt\floatc@alg
33 \def\@fs@pre{}\def\@fs@post{}\def\@fs@mid{\vspace{3pt}}
34 \let\@fs@iftopcapt\iftrue}
35 \floatstyle{alg}
36 \newfloat{algorithmfloat}{h}{loa}
37 \floatname{algorithmfloat}{\alg@floatname}

\listofalgorithms The \listofalgorithms macro can be used to generate a list of all algorithms in a document.

38 \newcommand{\listofalgorithms}{\listof{algorithmfloat}{\alg@listname}}

alg@margin The alg@margin environment makes the text a bit narrower. This environment is used in both the algorithm and algtab environments; it keeps track of if the text is already narrow, and in this case does nothing.

39 \newenvironment{alg@margin} {
40 \ifthenelse{\value{alg@inmargin}=0} {
41  \advance\leftskip\algmarginwidth
42  \advance\rightskip\algmarginwidth
43  \alg@fromleft=\leftskip
44 } {}
45 \stepcounter{alg@inmargin}

46 \parskip=0cm\parindent=0cm
47 } {%
48 \addtocounter{alg@inmargin}{-1}%
49 \ifthenelse{\value{alg@inmargin}=0} {%
50  \advance\leftskip-\algmarginwidth%
51  \advance\rightskip-\algmarginwidth%
52 } {}%

53 }

algorithm The algorithm environment simply begins a float as defined above. Actually, the default is to use the placement parameter H, so that the algorithm will not really float. Inside the float all text is indented by \algmarginwidth.

54 \newenvironment{algorithm}[1][H] {
55 \begin{algorithmfloat}[#1]\begin{alg@margin}
56 } {
57 \end{alg@margin}\end{algorithmfloat}

58 }

alg@tab The alg@tab environment is what does most of the formatting job; it’s called by algtab and algtab* defined below. The argument defines the amount of initial indentation. If the counter alg@inmargin is zero, alg@tab is not started within a float. In this case some room is made above and below it. Inside this environment, \\ is let to the macro alg@cr that is defined below.

59 \newenvironment{alg@tab}[1] {
60 \ifthenelse{\value{alg@inmargin}=0} {\vskip\baselineskip}{}
61 \begin{alg@margin}
62 \let\\=\alg@cr
63 \setcounter{algline}{1}
64 \advance\leftskip#1
65 \alg@putlineno\ignorespaces
66 } {
67 \setbox\alg@tmpbox=\lastbox
68 \ifhbox\alg@tmpbox{\vskip-\baselineskip}\else\par\fi
69 \end{alg@margin}
70 \ifthenelse{\value{alg@inmargin}=0}{\vskip\baselineskip}{}

71 }

algtab This environment sets alg@linenums true, which will make \algputlineno write the current line number in the left margin.

72 \newenvironment{algtab}[0][\alglinenowidth] {
73 \setboolean{alg@linenums}{true}\begin{alg@tab}{#1}
74 } {\end{alg@tab}}

algtab* The algtab* environment works like algtab but sets alg@linenums false and uses zero indentation by default.

75 \newenvironment{algtab*}[0][0cm] {
76 \setboolean{alg@linenums}{false}\begin{alg@tab}{#1}
77 } {\end{alg@tab}}

\alg@kill The \alg@kill macro removes the last box from the current horizontal list. It is used to remove the box containing the line number (label) when indentation is changed: in this case a new box for the label must be created.

78 \newcommand{\alg@kill}{\setbox\alg@tmpbox=\lastbox%
79 \ifvoid\alg@tmpbox\PackageError{alg}{Attempt to remove label
80  in middle of line}\fi}

\algbegin \algbegin adds to \leftskip and replaces the line number. It must only be used at the beginning of a line.

81 \newcommand{\algbegin}[0][\algtabwidth]{\advance\leftskip#1%
82 \alg@kill\alg@putlineno\ignorespaces}

\algend This macro reverses the effect of a previous \algbegin.

83 \newcommand{\algend}[0][\algtabwidth]{\advance\leftskip-1#1%
84 \alg@kill\alg@putlineno\ignorespaces}

\alg@cr New lines are started using this macro. The line number is incremented and printed.

85 \newcommand{\alg@cr}{\par\refstepcounter{algline}\alg@putlineno%
86 \ignorespaces}

\alg@putlineno Line numbers are typeset as labels.

87 \newcommand{\alg@putlineno}{%
88 \ifthenelse{\boolean{alg@linenums}} {%
89  \alg@putlabel{(\arabic{algline})}} {\alg@putlabel{}}}

\alg@putlabel This is the macro that puts a label on the horizontal list. The label extends to the left of a zero-width box.

90 \newcommand{\alg@putlabel}[1]{{%
91  \alg@tmplen=\leftskip \advance\alg@tmplen-\alg@fromleft%
92  \makebox[0cm][r]{\makebox[\alg@tmplen][l]{#1}}}}

3.1 Macros for the algorithm environment

93 \newcommand{\algdescript}[1]{\textbf{\alg@descname: }#1\par}
94 \newcommand{\alginout}[2]{\textbf{\alg@inputname: }#1\par
95 \textbf{\alg@outputname: }#2\par}
96 \newcommand{\algname}[2]{\textsc{#1}(#2)\par}

3.2 Macros for referencing

97 \newcommand{\alglabel}[1]{%
98 \ifthenelse{\boolean{alg@linenums}}{%
99  \label{#1}}{\alg@kill\alg@putlabel{#1}}\ignorespaces}
100 \newcommand{\algref}[1]{\ifthenelse{\boolean{alg@linenums}}%
101 {\ref{#1}}{#1}}

3.3 Macros for the algtab environment

102 \newcommand{\algand}{\mbox{\textbf{and }}}
103 \newcommand{\algcall}[2]{\textsc{#1}(#2)}
104 \newcommand{\algcase}[1]{\algend\textbf{case} #1\\\algbegin}
105 \newcommand{\algdefault}{\algend\textbf{default}\\\algbegin}
106 \newcommand{\algelse}{\algend\textbf{else}\\\algbegin}
107 \newcommand{\algelsif}[1]{\algend\textbf{else if} #1\\\algbegin}
108 \newcommand{\algerror}{\textbf{error }}
109 \newcommand{\algfalse}{\mbox{\textbf{false }}}
110 \newcommand{\algforto}[2]{\textbf{for} #1 \textbf{to} #2\\\algbegin}
111 \newcommand{\algforeach}[1]{\textbf{foreach} #1\\\algbegin}
112 \newcommand{\alggoto}{\textbf{goto~}}
113 \newcommand{\algif}[1]{\textbf{if} #1\\\algbegin}
114 \newcommand{\algifthen}[2]{\textbf{if} #1 \textbf{then} #2\\}
115 \newcommand{\algifthenelse}[3]{\setbox\alg@tmpbox=
116 \hbox{\textbf{if} #1 }\copy\alg@tmpbox\textbf{then} #2\\
117 \settowidth{\alg@tmplen}{\box\alg@tmpbox}%
118 \algbegin[\alg@tmplen]\textbf{else} #3\\ \algend[\alg@tmplen]}
119 \newcommand{\algnot}{\mbox{\textbf{not }}}
120 \newcommand{\algor}{\mbox{\textbf{or }}}
121 \newcommand{\algpardo}{\mbox{\textbf{pardo}}}
122 \newcommand{\algprint}{\textbf{print }}
123 \newcommand{\algrepeat}{\textbf{repeat}\\\algbegin}
124 \newcommand{\algreturn}{\textbf{return~}}
125 \newcommand{\algswitch}[1]{\textbf{switch} #1\\\algbegin}
126 \newcommand{\algtrue}{\mbox{\textbf{true }}}
127 \newcommand{\alguntil}[1]{\algend\textbf{until} #1\ \\}
128 \newcommand{\algwhile}[1]{\textbf{while} #1\\\algbegin}

129 ⟨/package⟩