Debian Codegraph @

texmf-dist/source/latex/alg/alg.dtx

raw
1 \def\filedate{13 March 2001}
2 % \iffalse
3 %% alg.dtx
4 %% Copyright (c) 1995, 1999, 2001 Staffan Ulfberg
5 %
6 % This program can redistributed and/or modified under the terms
7 % of the LaTeX Project Public License Distributed from CTAN
8 % archives in directory macros/latex/base/lppl.txt; either
9 % version 1 of the License, or (at your option) any later version.
10 %
11 %<package>\NeedsTeXFormat{LaTeX2e}[1996/12/01]
12 %<package>\ProvidesPackage{alg}
13 %<package> [2001/02/12]
14 %
15 %<*driver>
16 \documentclass{ltxdoc}
17 \usepackage{alg}
18 \DisableCrossrefs
19 \setlength{\parindent}{0pt}
20 \begin{document}
21 \title{The \textsf{alg} package\thanks{This file was last
22 revised \filedate.}}
23 \author{Staffan Ulfberg\\[email protected]}
24 \date{\filedate}
25 \maketitle
26 \DocInput{alg.dtx}
27 \end{document}
28 %</driver>
29 % \fi
30 %
31 % \begin{abstract}
32 % This package defines two environments for typesetting algorithms in
33 % \LaTeXe\@. Lines are automatically numbered and can be referenced,
34 % the means for easy indentation is provided, and algorithms can be made
35 % floating bodies if desired.
36 % \end{abstract}
37 %
38 % \section{Introduction}
39 % |alg.sty| defines two environments. The \DescribeEnv{algtab} |algtab|
40 % environment is used to typeset an algorithm with automatically
41 % numbered lines; it also takes care of indentation. The
42 % \DescribeEnv{algorithm} |algorithm| environment can be used to
43 % encapsulate the |algtab| environment in a floating body together
44 % with a header, a caption, etc.
45 %
46 % The package recognizes a few language options and changes its fixed
47 % output strings accordingly. Please tell the author of this package
48 % if you need support for another language!
49 %
50 % \subsection{The \texttt{algorithm} environment}
51 %
52 % The |algorithm| environment starts a floating body; its placement
53 % is decided by an optional agrument that can be any combination of
54 % |t|, |b|, |p|, or |h|. By default, the placement |H| (Here!) is
55 % used, so the float does not float after all. See the
56 % description of the \textsf{float} package by Anselm Lingnau for
57 % more details about this.
58 %
59 % Inside the |algorithm| environment, the text will be indented from
60 % the left and right edges. It is possible to put a |\caption| within
61 % the float, and also to generate a list of algorithms with the
62 % \DescribeMacro{\listofalgorithms} |\listofalgorithms| command.
63 %
64 % Notice that it is by no means necessary to use this environment to
65 % use the rest of the package.
66 %
67 % \subsection{Algorithm description}
68 %
69 % Three macros are defined to describe an algorithm's name,
70 % parameters, and function. They may be used in the |algorithm|
71 % environment, or just anywhere before the |algtab| environment.
72 % \begin{description}
73 % \item[\texttt{\bslash algname}] \DescribeMacro{\algname}
74 % takes two arguments of which the first is printed using small caps,
75 % followed by the second in parentheses.
76 % \item[\texttt{\bslash algdescript}] \DescribeMacro{\algdescript}
77 % takes one argument which is printed after the string
78 % ``Description:'' in boldface letters.
79 % \item[\texttt{\bslash alginout}] \DescribeMacro{\alginout}
80 % takes two arguments which are printed after the strings
81 % ``Input:'' and ``Output:'' respectively.
82 % \end{description}
83 %
84 % \subsection{The \texttt{algtab} environment}
85 %
86 % In the |algtab| environment, an algorithm is typed line by line,
87 % separating lines by~|\\|. Every time a new line is started, it will
88 % be numbered in the left margin starting at line~1. A single
89 % ``line'' of the algorithm can span several lines of the page,
90 % but a line number will only be printed after each |\\| command. The
91 % current |\ref| value is also set, so that a label can be entered; it's
92 % recommended that \DescribeMacro{\alglabel}|\alglabel| is used for this
93 % purpose.
94 %
95 % The |algtab| environment has a star-form \DescribeEnv{algtab*} variant
96 % that supresses line number generation; if the |\alglabel| macro is
97 % used in this case, the supplied label argument is printed as-is in the
98 % left margin of the algorithm (where the line numbers usually are
99 % printed). The macro \DescribeMacro{\algref} |\algref| corresponds
100 % to |\alglabel| in the way that it prints either the referenced
101 % label's value, or the label name literally if no line numbers are
102 % used. However, |\algref| can't be used outside the |algtab|
103 % environment: use |\ref| intead.
104 %
105 % The \DescribeMacro{\algnonumber} |\algnonumber| macro can be used at the
106 % start of a line to suppress the printing of a line number on that line.
107 %
108 % The |algtab| environment indents the algorithm to make room for the
109 % line numbers; the |algtab*| does not indent the algorithm by default.
110 % However, both environments take an optional argument specifying the
111 % amount of indentation that is desired.
112 %
113 % There are two important macros, \DescribeMacro{\algbegin} |\algbegin|
114 % and \DescribeMacro{\algend} |\algend|, defined in the |algtab|
115 % environment. These macros start and stop additional indentation
116 % respectively; they should always be used at the beginning of a line.
117 % These macros are already included in some of the macros that are
118 % special to the |algtab| environment.
119 %
120 % \DeleteShortVerb{\|}
121 %
122 % \begin{algorithm}[h]
123 % \caption{Example of the \texttt{algorithm} environment.\label{alg:ex}}
124 % \alginout{An ordered set $U=\{u_1,u_2,\dots,u_n\}$.}
125 % {The set's maximum element, and a set $A$, $|A|=\log n$,
126 % containing the next largest element. (If $n=1$, then
127 % $A=\emptyset$).}
128 % \algname{Max2}{$U$}
129 % \begin{algtab}
130 % \algif{$|U|=1$}
131 % \algreturn $(u_1, \emptyset)$ \\
132 % \algelsif{$|U|=2$}
133 % \algifthenelse{$u_1>u_2$}{\algreturn $(u_1, \{u_2\})$}
134 % {\algreturn $(u_2, \{u_1\})$}
135 % \algelse
136 % $(b,B) \leftarrow$
137 % \algcall{Max2}{$\{u_i\}_{i=1}^{\lfloor n/2\rfloor}$}\\
138 % $(c,C) \leftarrow$
139 % \algcall{Max2}{$\{u_i\}_{i=\lfloor n/2\rfloor+1}^{n}$}\\
140 % \algifthenelse{$b>c$}{\algreturn $(b, \{c\}\cup B)$}
141 % {\algreturn $(c, \{b\}\cup C)$}
142 % \algend
143 % \end{algtab}
144 % \end{algorithm}
145 %
146 % \MakeShortVerb{\|}
147 %
148 % \section{Example}
149 %
150 % This section shows how to typeset Algorithm~\ref{alg:ex} using the
151 % \textsf{alg} package in \LaTeXe:
152 %
153 % \DeleteShortVerb{\|}
154 %
155 % \begin{verbatim}
156 % \begin{algorithm}[h]
157 % \caption{Example of the \texttt{algorithm} environment.\label{alg:ex}}
158 % \alginout{An ordered set $U=\{u_1,u_2,\dots,u_n\}$.}
159 % {The set's maximum element, and a set $A$, $|A|=\log n$,
160 % containing the next largest element. (If $n=1$, then
161 % $A=\emptyset$).}
162 % \algname{Max2}{$U$}
163 % \begin{algtab}
164 % \algif{$|U|=1$}
165 % \algreturn $(u_1, \emptyset)$ \\
166 % \algelsif{$|U|=2$}
167 % \algifthenelse{$u_1>u_2$}{\algreturn $(u_1, \{u_2\})$}
168 % {\algreturn $(u_2, \{u_1\})$}
169 % \algelse
170 % $(b,B) \leftarrow$
171 % \algcall{Max2}{$\{u_i\}_{i=1}^{\lfloor n/2\rfloor}$}\\
172 % $(c,C) \leftarrow$
173 % \algcall{Max2}{$\{u_i\}_{i=\lfloor n/2\rfloor+1}^{n}$}\\
174 % \algifthenelse{$b>c$}{\algreturn $(b, \{c\}\cup B)$}
175 % {\algreturn $(c, \{b\}\cup C)$}
176 % \algend
177 % \end{algtab}
178 % \end{algorithm}
179 % \end{verbatim}
180 %
181 % \MakeShortVerb{\|}
182 %
183 % There is a list of all programming constructs available in the
184 % |algtab| environment at the end of this document. They work
185 % very much like the macros used above. As a general rule, if a macro
186 % doesn't take an argument, a space charater is included at the end of
187 % the macro definition. For example, type |$a=0$ \algor \algnot $b=0$|
188 % to produce ``$a=0$ \algor \algnot $b=0$.''
189 %
190 % \section{The Implementation}
191 %
192 % \begin{macrocode}
193 %<*package>
194 % \end{macrocode}
195 %
196 % The |float| package by Anselm Lingnau is used for floating algorithms.
197 % \begin{macrocode}
198 \RequirePackage{float, ifthen}
199 % \end{macrocode}
200 %
201 % Here are the variable declarations. |\algleftmarginwidth|,
202 % |\algrightmarginwidth|, |\alglinenowidth|,
203 % and |\algtabwidth| define the amount of indentation of the entire
204 % algorithm, the space reserved for line numbers, and the indentation
205 % made by |\algbegin| respectively.
206 % \begin{macrocode}
207 \newlength{\algleftmarginwidth}\setlength{\algleftmarginwidth}{.5in}
208 \newlength{\algrightmarginwidth}\setlength{\algrightmarginwidth}{.5in}
209 \newlength{\alglinenowidth}\setlength{\alglinenowidth}{1.2cm}
210 \newlength{\algtabwidth}\setlength{\algtabwidth}{.5cm}
211 \newlength{\alg@fromleft}
212 \newlength{\alg@tmplen}
213 \newsavebox{\alg@tmpbox}
214 \newcounter{alg@inmargin}\setcounter{alg@inmargin}{0}
215 \newcounter{algline}
216 \newboolean{alg@linenums}
217 \newboolean{alg@nonumber}
218 % \end{macrocode}
219 %
220 % Strings used in captions and in the List of Algorithms differ in some
221 % languages. If a language is specified as an option to this package,
222 % that language is used. Otherwise, if the babel package is loaded, the
223 % selected babel lanugage is used.
224 % \begin{macrocode}
225 \def\alg@language{english}
226 \@ifpackageloaded{babel}{
227 \iflanguage{english}{\def\alg@language{english}}{}
228 \iflanguage{american}{\def\alg@language{american}}{}
229 \iflanguage{swedish}{\def\alg@language{swedish}}{}
230 \iflanguage{french}{\def\alg@language{french}}{}
231 \iflanguage{german}{\def\alg@language{german}}{}}{}
232 \DeclareOption{english}{\def\alg@language{english}}
233 \DeclareOption{american}{\def\alg@language{american}}
234 \DeclareOption{swedish}{\def\alg@language{swedish}}
235 \DeclareOption{french}{\def\alg@language{french}}
236 \DeclareOption{german}{\def\alg@language{german}}
237 \ProcessOptions
238 \ifthenelse{\equal{\alg@language}{english}}{
239 \def\alg@floatname{Algorithm}
240 \def\alg@listname{List of Algorithms}
241 \def\alg@descname{Description}
242 \def\alg@inputname{Input}
243 \def\alg@outputname{Output}}{}
244 \ifthenelse{\equal{\alg@language}{american}}{
245 \def\alg@floatname{Algorithm}
246 \def\alg@listname{List of Algorithms}
247 \def\alg@descname{Description}
248 \def\alg@inputname{Input}
249 \def\alg@outputname{Output}}{}
250 \ifthenelse{\equal{\alg@language}{swedish}}{
251 \def\alg@floatname{Algoritm}
252 \def\alg@listname{Algoritmer}
253 \def\alg@descname{Beskrivning}
254 \def\alg@inputname{Input}
255 \def\alg@outputname{Output}}{}
256 \ifthenelse{\equal{\alg@language}{french}}{
257 \def\alg@floatname{Algorithme}
258 \def\alg@listname{Liste des algorithmes}
259 \def\alg@descname{Description}
260 \def\alg@inputname{Entr\'{e}e}
261 \def\alg@outputname{Sortie}}{}
262 \ifthenelse{\equal{\alg@language}{german}}{
263 \def\alg@floatname{Algorithmus}
264 \def\alg@listname{Algorithmenverzeichnis}
265 \def\alg@descname{Beschreibung}
266 \def\alg@inputname{Eingabe}
267 \def\alg@outputname{Ausgabe}}{}
268 % \end{macrocode}
269 %
270 % The following definitions set up the properties of the
271 % |algorithmfloat|.
272 % \begin{macrocode}
273 \newcommand\floatc@alg[2]{{\bfseries\rmfamily
274 \hspace{\algleftmarginwidth}#1:} #2\par}
275 \newcommand\fs@alg{
276 \let\@fs@capt\floatc@alg
277 \def\@fs@pre{}\def\@fs@post{}\def\@fs@mid{\vspace{3pt}}
278 \let\@fs@iftopcapt\iftrue}
279 \floatstyle{alg}
280 \newfloat{algorithmfloat}{h}{loa}
281 \floatname{algorithmfloat}{\alg@floatname}
282 % \end{macrocode}
283 %
284 % \begin{macro}{\listofalgorithms}
285 % The |\listofalgorithms| macro can be used to generate a list of all
286 % algorithms in a document.
287 % \begin{macrocode}
288 \newcommand{\listofalgorithms}{\listof{algorithmfloat}{\alg@listname}}
289 % \end{macrocode}
290 % \end{macro}
291 %
292 % \begin{macro}{\alg@margin}
293 % The |alg@margin| macro makes the text a bit narrower. It is used in
294 % the start of both the |algorithm| and |algtab| environments, and also
295 % in the |algname|, |algdescript|, and |alginout| macros ; it keeps
296 % track of if the text is already narrow, and in this case does nothing.
297 % \begin{macrocode}
298 \newcommand{\alg@margin} {
299 \ifthenelse{\value{alg@inmargin}=0} {
300 \advance\leftskip\algleftmarginwidth
301 \advance\rightskip\algrightmarginwidth
302 \alg@fromleft=\leftskip
303 } {}
304 \stepcounter{alg@inmargin}
305 \parskip=0cm\parindent=0cm
306 }
307 % \end{macrocode}
308 % \end{macro}
309 %
310 % \begin{macro}{\alg@unmargin}
311 % The |alg@unmargin| macro resets any indentation made by |alg@margin|.
312 % \begin{macrocode}
313 \newcommand{\alg@unmargin} {
314 \addtocounter{alg@inmargin}{-1}%
315 \advance\leftskip-\algleftmarginwidth%
316 \advance\rightskip-\algrightmarginwidth%
317 }
318 % \end{macrocode}
319 % \end{macro}
320 %
321 % \begin{environment}{algorithm}
322 % The |algorithm| environment simply begins a float as defined above.
323 % Actually, the default is to use the placement parameter |H|, so that
324 % the algorithm will not really float. Inside the float all text is
325 % indented by |\algleftmarginwidth| and |\algrightmarginwidth|.
326 % \begin{macrocode}
327 \newenvironment{algorithm}[1][H] {
328 \begin{algorithmfloat}[#1]\alg@margin
329 } {
330 \alg@unmargin\end{algorithmfloat}
331 }
332 % \end{macrocode}
333 % \end{environment}
334 %
335 % \begin{environment}{alg@tab}
336 % The |alg@tab| environment is what does most of the formatting job;
337 % it's called by |algtab| and |algtab*| defined below. The argument
338 % defines the amount of initial indentation. If the counter
339 % |alg@inmargin| is zero, |alg@tab| is not started within a float. In
340 % this case some room is made above and below it. Inside this
341 % environment, |\\| is let to the macro |alg@cr| that is used to
342 % begin new lines. The |catcode| for |^^M| is changed to admit blank
343 % input lines within an algorithm.
344 % \begin{macrocode}
345 \newenvironment{alg@tab}[1] {
346 \setboolean{alg@nonumber}{false}%
347 \ifthenelse{\value{alg@inmargin}=0} {\vskip\baselineskip}{}
348 \alg@margin
349 \let\\=\alg@cr
350 \catcode`\^^M=10
351 \setcounter{algline}{0}\refstepcounter{algline}
352 \advance\leftskip#1
353 \alg@putlineno\ignorespaces
354 } {
355 \setbox\alg@tmpbox=\lastbox
356 \ifhbox\alg@tmpbox{\vskip-\baselineskip}\else\par\fi
357 \alg@unmargin
358 \ifthenelse{\value{alg@inmargin}=0}{\vskip\baselineskip}{}
359 }
360 % \end{macrocode}
361 % \end{environment}
362 %
363 % \begin{environment}{algtab}
364 % This environment sets |alg@linenums| true, which will make
365 % |\algputlineno| write the current line number in the left margin.
366 % \begin{macrocode}
367 \newenvironment{algtab}[1][\alglinenowidth] {
368 \setboolean{alg@linenums}{true}\begin{alg@tab}{#1}
369 } {\end{alg@tab}}
370 % \end{macrocode}
371 % \end{environment}
372 %
373 % \begin{environment}{algtab*}
374 % The |algtab*| environment works like |algtab| but sets |alg@linenums|
375 % false and uses zero indentation by default.
376 % \begin{macrocode}
377 \newenvironment{algtab*}[1][0cm] {
378 \setboolean{alg@linenums}{false}\begin{alg@tab}{#1}
379 } {\end{alg@tab}}
380 % \end{macrocode}
381 % \end{environment}
382 %
383 % \begin{macro}{\alg@kill}
384 % The |\alg@kill| macro removes the last box from the current
385 % horizontal list. It is used to remove the box containing the line
386 % number (label) when indentation is changed: in this case a new box
387 % for the label must be created.
388 % \begin{macrocode}
389 \newcommand{\alg@kill}{\setbox\alg@tmpbox=\lastbox%
390 \ifvoid\alg@tmpbox\PackageError{alg}{Attempt to remove label
391 in middle of line}\fi}
392 % \end{macrocode}
393 % \end{macro}
394 %
395 % \begin{macro}{\algbegin}
396 % |\algbegin| adds to |\leftskip| and replaces the line number. It
397 % must only be used at the beginning of a line.
398 % \begin{macrocode}
399 \newcommand{\algbegin}[1][\algtabwidth]{\advance\leftskip#1%
400 \alg@kill\alg@putlineno\ignorespaces}
401 % \end{macrocode}
402 % \end{macro}
403 %
404 % \begin{macro}{\algend}
405 % This macro reverses the effect of a previous |\algbegin|.
406 % \begin{macrocode}
407 \newcommand{\algend}[1][\algtabwidth]{\advance\leftskip-1#1%
408 \alg@kill\alg@putlineno\ignorespaces}
409 % \end{macrocode}
410 % \end{macro}
411 %
412 % \begin{macro}{\algnonumber}
413 % \begin{macrocode}
414 \newcommand{\algnonumber}{\alg@kill\alg@putlabel{}%
415 \setboolean{alg@nonumber}{true}\ignorespaces}
416 % \end{macrocode}
417 % \end{macro}
418 %
419 % \begin{macro}{\alg@cr}
420 % New lines are started using this macro. The line number is
421 % incremented and printed.
422 % \begin{macrocode}
423 \newcommand{\alg@cr}{\par\refstepcounter{algline}%
424 \setboolean{alg@nonumber}{false}\alg@putlineno\ignorespaces}
425 % \end{macrocode}
426 % \end{macro}
427 %
428 % \begin{macro}{\alg@putlineno}
429 % Line numbers are typeset as labels.
430 % \begin{macrocode}
431 \newcommand{\alg@putlineno} {%
432 \ifthenelse{\boolean{alg@linenums}} {%
433 \ifthenelse{\boolean{alg@nonumber}}{\alg@putlabel{}} {%
434 \alg@putlabel{(\arabic{algline})}}}%
435 {\alg@putlabel{}}}
436 % \end{macrocode}
437 % \end{macro}
438 %
439 % \begin{macro}{\alg@putlabel}
440 % This is the macro that puts a label on the horizontal list. The
441 % label extends to the left of a zero-width box.
442 % \begin{macrocode}
443 \newcommand{\alg@putlabel}[1]{{%
444 \alg@tmplen=\leftskip \advance\alg@tmplen-\alg@fromleft%
445 \makebox[0cm][r]{\makebox[\alg@tmplen][l]{#1}}}}
446 % \end{macrocode}
447 % \end{macro}
448 %
449 % \subsection{Macros for algorithm descriptions}
450 %
451 % \begin{macrocode}
452 \newcommand{\algdescript}[1]{\alg@margin\textbf{\alg@descname: }#1\par}
453 \newcommand{\alginout}[2]{\alg@margin\textbf{\alg@inputname: }#1\par
454 \textbf{\alg@outputname: }#2\par}
455 \newcommand{\algname}[2]{\alg@margin\textsc{#1}(#2)\par}
456 % \end{macrocode}
457 %
458 % \subsection{Macros for referencing}
459 %
460 % \begin{macrocode}
461 \newcommand{\alglabel}[1]{%
462 \ifthenelse{\boolean{alg@linenums}}{%
463 \label{#1}}{\alg@kill\alg@putlabel{#1}}\ignorespaces}
464 \newcommand{\algref}[1]{\ifthenelse{\boolean{alg@linenums}}%
465 {\ref{#1}}{#1}}
466 % \end{macrocode}
467 %
468 % \subsection{Macros for the \texttt{algtab} environment}
469 %
470 % \begin{macrocode}
471 \newcommand{\algand}{\mbox{\textbf{and }}}
472 \newcommand{\algbreak}{\textbf{break}}
473 \newcommand{\algcall}[2]{\textsc{#1}(#2)}
474 \newcommand{\algcase}[1]{\algend\textbf{case} #1\\\algbegin}
475 \newcommand{\algcontinue}{\textbf{continue}}
476 \newcommand{\algdefault}{\algend\textbf{default}\\\algbegin}
477 \newcommand{\algelse}{\algend\textbf{else}\\\algbegin}
478 \newcommand{\algelseif}[1]{\algelsif{#1}}
479 \newcommand{\algelsif}[1]{\algend\textbf{else if} #1\\\algbegin}
480 \newcommand{\algerror}{\textbf{error }}
481 \newcommand{\algfalse}{\mbox{\textbf{false }}}
482 \newcommand{\algforto}[2]{\textbf{for} #1 \textbf{to} #2\\\algbegin}
483 \newcommand{\algforeach}[1]{\textbf{foreach} #1\\\algbegin}
484 \newcommand{\alggoto}{\textbf{goto~}}
485 \newcommand{\algif}[1]{\textbf{if} #1\\\algbegin}
486 \newcommand{\algifthen}[2]{\textbf{if} #1 \textbf{then} #2\\}
487 \newcommand{\algifthenelse}[3]{\setbox\alg@tmpbox=
488 \hbox{\textbf{if} #1 }\copy\alg@tmpbox\textbf{then} #2\\
489 \settowidth{\alg@tmplen}{\box\alg@tmpbox}%
490 \algbegin[\alg@tmplen]\textbf{else} #3\\ \algend[\alg@tmplen]}
491 \newcommand{\algnot}{\mbox{\textbf{not }}}
492 \newcommand{\algor}{\mbox{\textbf{or }}}
493 \newcommand{\algpardo}{\mbox{\textbf{pardo}}}
494 \newcommand{\algprint}{\textbf{print }}
495 \newcommand{\algrepeat}{\textbf{repeat}\\\algbegin}
496 \newcommand{\algreturn}{\textbf{return~}}
497 \newcommand{\algswitch}[1]{\textbf{switch} #1\\\algbegin}
498 \newcommand{\algtrue}{\mbox{\textbf{true }}}
499 \newcommand{\alguntil}[1]{\algend\textbf{until} #1\ \\}
500 \newcommand{\algwhile}[1]{\textbf{while} #1\\\algbegin}
501 % \end{macrocode}
502 %
503 % \begin{macrocode}
504 %</package>
505 % \end{macrocode}
506 %
507 % \Finale