summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/alg/alg.dtx
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /macros/latex/contrib/alg/alg.dtx
Initial commit
Diffstat (limited to 'macros/latex/contrib/alg/alg.dtx')
-rw-r--r--macros/latex/contrib/alg/alg.dtx507
1 files changed, 507 insertions, 0 deletions
diff --git a/macros/latex/contrib/alg/alg.dtx b/macros/latex/contrib/alg/alg.dtx
new file mode 100644
index 0000000000..b0e7e57f53
--- /dev/null
+++ b/macros/latex/contrib/alg/alg.dtx
@@ -0,0 +1,507 @@
+\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