\def\filedate{13 March 2001}
% \iffalse
%% alg.dtx
%% Copyright (c) 1995, 1999, 2001 Staffan Ulfberg
%
% This program can redistributed and/or modified under the terms
% of the LaTeX Project Public License Distributed from CTAN
% archives in directory macros/latex/base/lppl.txt; either
% version 1 of the License, or (at your option) any later version.
%
%<package>\NeedsTeXFormat{LaTeX2e}[1996/12/01]
%<package>\ProvidesPackage{alg}
%<package>         [2001/02/12]
%
%<*driver>
\documentclass{ltxdoc}
\usepackage{alg}
\DisableCrossrefs
\setlength{\parindent}{0pt}
\begin{document}
\title{The \textsf{alg} package\thanks{This file was last
       revised \filedate.}}
\author{Staffan Ulfberg\\staffan@ulfberg.se}
\date{\filedate}
\maketitle
\DocInput{alg.dtx}
\end{document}
%</driver>
% \fi
%
% \begin{abstract}
% This package defines two environments for typesetting algorithms in
% \LaTeXe\@.  Lines are automatically numbered and can be referenced,
% the means for easy indentation is provided, and algorithms can be made
% floating bodies if desired.
% \end{abstract}
%
% \section{Introduction}
% |alg.sty| defines two environments.  The \DescribeEnv{algtab} |algtab|
% environment is used to typeset an algorithm with automatically
% numbered lines; it also takes care of indentation.  The
% \DescribeEnv{algorithm} |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!
%
% \subsection{The \texttt{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 \textsf{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 a list of algorithms with the
% \DescribeMacro{\listofalgorithms} |\listofalgorithms| command.
%
% Notice that it is by no means necessary to use this environment to 
% use the rest of the package.
%
% \subsection{Algorithm description}
%
% Three macros are defined to describe an algorithm's name,
% parameters, and function.  They may be used in the |algorithm|
% environment, or just anywhere before the |algtab| environment.
% \begin{description}
% \item[\texttt{\bslash algname}] \DescribeMacro{\algname}
% takes two arguments of which the first is printed using small caps,
% followed by the second in parentheses.
% \item[\texttt{\bslash algdescript}] \DescribeMacro{\algdescript}
% takes one argument which is printed after the string
% ``Description:'' in boldface letters.
% \item[\texttt{\bslash alginout}] \DescribeMacro{\alginout}
% takes two arguments which are printed after the strings
% ``Input:'' and ``Output:'' respectively.
% \end{description}
% 
% \subsection{The \texttt{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 of 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 \DescribeMacro{\alglabel}|\alglabel| is used for this
% purpose.
% 
% The |algtab| environment has a star-form \DescribeEnv{algtab*} 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 are
% printed).  The macro \DescribeMacro{\algref} |\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 \DescribeMacro{\algnonumber} |\algnonumber| macro can be used at the
% start of a line to suppress the printing of a line number on that line.
%
% 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.
%
% There are two important macros,  \DescribeMacro{\algbegin} |\algbegin|
% and \DescribeMacro{\algend} |\algend|, defined in the |algtab|
% 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.
%  
% \DeleteShortVerb{\|}
%
% \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
%         $(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}
%
% \MakeShortVerb{\|}
%
% \section{Example}
%
% This section shows how to typeset Algorithm~\ref{alg:ex} using the
% \textsf{alg} package in \LaTeXe:
%
% \DeleteShortVerb{\|}
%
% \begin{verbatim}
% \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
%         $(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}
% \end{verbatim}
%
% \MakeShortVerb{\|}
% 
% 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$ \algor \algnot $b=0$.''
%
% \section{The Implementation}
%
%    \begin{macrocode}
%<*package>
%    \end{macrocode}
%
% The |float| package by Anselm Lingnau is used for floating algorithms.
%    \begin{macrocode}
\RequirePackage{float, ifthen}
%    \end{macrocode}
% 
% Here are the variable declarations.  |\algleftmarginwidth|,
% |\algrightmarginwidth|, |\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.
%    \begin{macrocode}
\newlength{\algleftmarginwidth}\setlength{\algleftmarginwidth}{.5in}
\newlength{\algrightmarginwidth}\setlength{\algrightmarginwidth}{.5in}
\newlength{\alglinenowidth}\setlength{\alglinenowidth}{1.2cm}
\newlength{\algtabwidth}\setlength{\algtabwidth}{.5cm}
\newlength{\alg@fromleft}
\newlength{\alg@tmplen}
\newsavebox{\alg@tmpbox}
\newcounter{alg@inmargin}\setcounter{alg@inmargin}{0}
\newcounter{algline}
\newboolean{alg@linenums}
\newboolean{alg@nonumber}
%    \end{macrocode}
%
% Strings used in captions and in the List of Algorithms differ in some
% languages.  If a language is specified as an option to this package,
% that language is used.  Otherwise, if the babel package is loaded, the
% selected babel lanugage is used.
%    \begin{macrocode}
\def\alg@language{english}
\@ifpackageloaded{babel}{
\iflanguage{english}{\def\alg@language{english}}{}
\iflanguage{american}{\def\alg@language{american}}{}
\iflanguage{swedish}{\def\alg@language{swedish}}{}
\iflanguage{french}{\def\alg@language{french}}{}
\iflanguage{german}{\def\alg@language{german}}{}}{}
\DeclareOption{english}{\def\alg@language{english}}
\DeclareOption{american}{\def\alg@language{american}}
\DeclareOption{swedish}{\def\alg@language{swedish}}
\DeclareOption{french}{\def\alg@language{french}}
\DeclareOption{german}{\def\alg@language{german}}
\ProcessOptions
\ifthenelse{\equal{\alg@language}{english}}{
	\def\alg@floatname{Algorithm}
	\def\alg@listname{List of Algorithms}
	\def\alg@descname{Description}
	\def\alg@inputname{Input}
	\def\alg@outputname{Output}}{}
\ifthenelse{\equal{\alg@language}{american}}{
	\def\alg@floatname{Algorithm}
	\def\alg@listname{List of Algorithms}
	\def\alg@descname{Description}
	\def\alg@inputname{Input}
	\def\alg@outputname{Output}}{}
\ifthenelse{\equal{\alg@language}{swedish}}{
	\def\alg@floatname{Algoritm}
	\def\alg@listname{Algoritmer}
	\def\alg@descname{Beskrivning}
	\def\alg@inputname{Input}
	\def\alg@outputname{Output}}{}
\ifthenelse{\equal{\alg@language}{french}}{
	\def\alg@floatname{Algorithme}
	\def\alg@listname{Liste des algorithmes}
	\def\alg@descname{Description}
	\def\alg@inputname{Entr\'{e}e}
	\def\alg@outputname{Sortie}}{}
\ifthenelse{\equal{\alg@language}{german}}{
	\def\alg@floatname{Algorithmus}
	\def\alg@listname{Algorithmenverzeichnis}
	\def\alg@descname{Beschreibung}
	\def\alg@inputname{Eingabe}
	\def\alg@outputname{Ausgabe}}{}
%    \end{macrocode}
%
% The following definitions set up the properties of the
% |algorithmfloat|.
%    \begin{macrocode}
\newcommand\floatc@alg[2]{{\bfseries\rmfamily
   \hspace{\algleftmarginwidth}#1:} #2\par}
\newcommand\fs@alg{
   \let\@fs@capt\floatc@alg
   \def\@fs@pre{}\def\@fs@post{}\def\@fs@mid{\vspace{3pt}}
   \let\@fs@iftopcapt\iftrue}
\floatstyle{alg}
\newfloat{algorithmfloat}{h}{loa}
\floatname{algorithmfloat}{\alg@floatname}
%    \end{macrocode}
%
% \begin{macro}{\listofalgorithms}
% The |\listofalgorithms| macro can be used to generate a list of all
% algorithms in a document.
%    \begin{macrocode}
\newcommand{\listofalgorithms}{\listof{algorithmfloat}{\alg@listname}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\alg@margin}
% The |alg@margin| macro makes the text a bit narrower.  It is used in
% the start of both the |algorithm| and |algtab| environments, and also
% in the |algname|, |algdescript|, and |alginout| macros ; it keeps
% track of if the text is already narrow, and in this case does nothing.
%    \begin{macrocode}
\newcommand{\alg@margin} {
   \ifthenelse{\value{alg@inmargin}=0} {
       \advance\leftskip\algleftmarginwidth
       \advance\rightskip\algrightmarginwidth
       \alg@fromleft=\leftskip
   } {}
   \stepcounter{alg@inmargin}
   \parskip=0cm\parindent=0cm
}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\alg@unmargin}
% The |alg@unmargin| macro resets any indentation made by |alg@margin|.
%    \begin{macrocode}
\newcommand{\alg@unmargin} {
   \addtocounter{alg@inmargin}{-1}%
   \advance\leftskip-\algleftmarginwidth%
   \advance\rightskip-\algrightmarginwidth%
}
%    \end{macrocode}
% \end{macro}
%
% \begin{environment}{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 |\algleftmarginwidth| and |\algrightmarginwidth|.
%    \begin{macrocode}
\newenvironment{algorithm}[1][H] {
   \begin{algorithmfloat}[#1]\alg@margin
} {
   \alg@unmargin\end{algorithmfloat}
}
%    \end{macrocode}
% \end{environment}
%
% \begin{environment}{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 used to 
% begin new lines.  The |catcode| for |^^M| is changed to admit blank
% input lines within an algorithm.
%    \begin{macrocode}
\newenvironment{alg@tab}[1] {
   \setboolean{alg@nonumber}{false}%
   \ifthenelse{\value{alg@inmargin}=0} {\vskip\baselineskip}{}
   \alg@margin
   \let\\=\alg@cr
   \catcode`\^^M=10
   \setcounter{algline}{0}\refstepcounter{algline}
   \advance\leftskip#1
   \alg@putlineno\ignorespaces
} {
   \setbox\alg@tmpbox=\lastbox
   \ifhbox\alg@tmpbox{\vskip-\baselineskip}\else\par\fi
   \alg@unmargin
   \ifthenelse{\value{alg@inmargin}=0}{\vskip\baselineskip}{}
}
%    \end{macrocode}
% \end{environment}
%
% \begin{environment}{algtab}
% This environment sets |alg@linenums| true, which will make
% |\algputlineno| write the current line number in the left margin.
%    \begin{macrocode}
\newenvironment{algtab}[1][\alglinenowidth] {
   \setboolean{alg@linenums}{true}\begin{alg@tab}{#1}
} {\end{alg@tab}}
%    \end{macrocode}
% \end{environment}
%
% \begin{environment}{algtab*}
% The |algtab*| environment works like |algtab| but sets |alg@linenums|
% false and uses zero indentation by default.
%    \begin{macrocode}
\newenvironment{algtab*}[1][0cm] {
   \setboolean{alg@linenums}{false}\begin{alg@tab}{#1}
} {\end{alg@tab}}
%    \end{macrocode}
% \end{environment}
%
% \begin{macro}{\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.
%    \begin{macrocode}
\newcommand{\alg@kill}{\setbox\alg@tmpbox=\lastbox%
   \ifvoid\alg@tmpbox\PackageError{alg}{Attempt to remove label
      in middle of line}\fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\algbegin}
% |\algbegin| adds to |\leftskip| and replaces the line number.  It
% must only be used at the beginning of a line.
%    \begin{macrocode}
\newcommand{\algbegin}[1][\algtabwidth]{\advance\leftskip#1%
   \alg@kill\alg@putlineno\ignorespaces}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\algend}
% This macro reverses the effect of a previous |\algbegin|.
%    \begin{macrocode}
\newcommand{\algend}[1][\algtabwidth]{\advance\leftskip-1#1%
   \alg@kill\alg@putlineno\ignorespaces}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\algnonumber}
%    \begin{macrocode}
\newcommand{\algnonumber}{\alg@kill\alg@putlabel{}%
   \setboolean{alg@nonumber}{true}\ignorespaces}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\alg@cr}
% New lines are started using this macro.  The line number is
% incremented and printed.
%    \begin{macrocode}
\newcommand{\alg@cr}{\par\refstepcounter{algline}%
   \setboolean{alg@nonumber}{false}\alg@putlineno\ignorespaces}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\alg@putlineno}
% Line numbers are typeset as labels.
%    \begin{macrocode}
\newcommand{\alg@putlineno} {%
   \ifthenelse{\boolean{alg@linenums}} {%
      \ifthenelse{\boolean{alg@nonumber}}{\alg@putlabel{}} {%
         \alg@putlabel{(\arabic{algline})}}}%
      {\alg@putlabel{}}}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\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.
%    \begin{macrocode}
\newcommand{\alg@putlabel}[1]{{%
      \alg@tmplen=\leftskip \advance\alg@tmplen-\alg@fromleft%
      \makebox[0cm][r]{\makebox[\alg@tmplen][l]{#1}}}}
%    \end{macrocode}
% \end{macro}
%
% \subsection{Macros for algorithm descriptions}
% 
%    \begin{macrocode}
\newcommand{\algdescript}[1]{\alg@margin\textbf{\alg@descname: }#1\par}
\newcommand{\alginout}[2]{\alg@margin\textbf{\alg@inputname: }#1\par
   \textbf{\alg@outputname: }#2\par}
\newcommand{\algname}[2]{\alg@margin\textsc{#1}(#2)\par}
%    \end{macrocode}
%
% \subsection{Macros for referencing}
% 
%    \begin{macrocode}
\newcommand{\alglabel}[1]{%
   \ifthenelse{\boolean{alg@linenums}}{%
      \label{#1}}{\alg@kill\alg@putlabel{#1}}\ignorespaces}
\newcommand{\algref}[1]{\ifthenelse{\boolean{alg@linenums}}%
   {\ref{#1}}{#1}}
%    \end{macrocode}
%
% \subsection{Macros for the \texttt{algtab} environment}
%
%    \begin{macrocode}
\newcommand{\algand}{\mbox{\textbf{and }}}
\newcommand{\algbreak}{\textbf{break}}
\newcommand{\algcall}[2]{\textsc{#1}(#2)}
\newcommand{\algcase}[1]{\algend\textbf{case} #1\\\algbegin}
\newcommand{\algcontinue}{\textbf{continue}}
\newcommand{\algdefault}{\algend\textbf{default}\\\algbegin}
\newcommand{\algelse}{\algend\textbf{else}\\\algbegin}
\newcommand{\algelseif}[1]{\algelsif{#1}}
\newcommand{\algelsif}[1]{\algend\textbf{else if} #1\\\algbegin}
\newcommand{\algerror}{\textbf{error }}
\newcommand{\algfalse}{\mbox{\textbf{false }}}
\newcommand{\algforto}[2]{\textbf{for} #1 \textbf{to} #2\\\algbegin}
\newcommand{\algforeach}[1]{\textbf{foreach} #1\\\algbegin}
\newcommand{\alggoto}{\textbf{goto~}}
\newcommand{\algif}[1]{\textbf{if} #1\\\algbegin}
\newcommand{\algifthen}[2]{\textbf{if} #1 \textbf{then} #2\\}
\newcommand{\algifthenelse}[3]{\setbox\alg@tmpbox=
   \hbox{\textbf{if} #1 }\copy\alg@tmpbox\textbf{then} #2\\
   \settowidth{\alg@tmplen}{\box\alg@tmpbox}%
   \algbegin[\alg@tmplen]\textbf{else} #3\\ \algend[\alg@tmplen]}
\newcommand{\algnot}{\mbox{\textbf{not }}}
\newcommand{\algor}{\mbox{\textbf{or }}}
\newcommand{\algpardo}{\mbox{\textbf{pardo}}}
\newcommand{\algprint}{\textbf{print }}
\newcommand{\algrepeat}{\textbf{repeat}\\\algbegin}
\newcommand{\algreturn}{\textbf{return~}}
\newcommand{\algswitch}[1]{\textbf{switch} #1\\\algbegin}
\newcommand{\algtrue}{\mbox{\textbf{true }}}
\newcommand{\alguntil}[1]{\algend\textbf{until} #1\ \\}
\newcommand{\algwhile}[1]{\textbf{while} #1\\\algbegin}
%    \end{macrocode}
%
%    \begin{macrocode}
%</package>
%    \end{macrocode}
%
% \Finale