summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/clrscode
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/clrscode
Initial commit
Diffstat (limited to 'macros/latex/contrib/clrscode')
-rw-r--r--macros/latex/contrib/clrscode/README2
-rw-r--r--macros/latex/contrib/clrscode/clrscode.pdfbin0 -> 38588 bytes
-rw-r--r--macros/latex/contrib/clrscode/clrscode.sty288
-rw-r--r--macros/latex/contrib/clrscode/clrscode.tex744
-rw-r--r--macros/latex/contrib/clrscode/page.tex18
5 files changed, 1052 insertions, 0 deletions
diff --git a/macros/latex/contrib/clrscode/README b/macros/latex/contrib/clrscode/README
new file mode 100644
index 0000000000..a68d0a8c9b
--- /dev/null
+++ b/macros/latex/contrib/clrscode/README
@@ -0,0 +1,2 @@
+Use this package to typeset pseudocode in the style of Introduction
+to Algorithms (second edition) by Cormen, Leiserson, Rivest, and Stein. \ No newline at end of file
diff --git a/macros/latex/contrib/clrscode/clrscode.pdf b/macros/latex/contrib/clrscode/clrscode.pdf
new file mode 100644
index 0000000000..4d1009eaa6
--- /dev/null
+++ b/macros/latex/contrib/clrscode/clrscode.pdf
Binary files differ
diff --git a/macros/latex/contrib/clrscode/clrscode.sty b/macros/latex/contrib/clrscode/clrscode.sty
new file mode 100644
index 0000000000..02061ae12e
--- /dev/null
+++ b/macros/latex/contrib/clrscode/clrscode.sty
@@ -0,0 +1,288 @@
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+% clrscode.sty
+
+% $Id: clrscode.sty,v 1.7 2007/03/29 19:12:30 thc Exp $
+% $Log: clrscode.sty,v $
+% Revision 1.7 2007/03/29 19:12:30 thc
+% Added date and version information to the \ProvidesPackage command.
+%
+% Revision 1.6 2005/07/14 20:55:00 thc
+% Added a definition for \numref. Thanks to Matt Suder(?) and Johan Gade.
+%
+% Revision 1.5 2003/11/11 15:45:37 thc
+% Removed a macro that is no longer needed.
+%
+% Revision 1.4 2003/11/07 20:23:16 thc
+% Fixed a bug that caused incorrect behavior when the \zi command
+% is used for lines beginning with \Until, \Else, \ElseIf, or \ElseNoIf.
+% Thanks for Oliver Ernst for reporting this bug.
+%
+% Revision 1.3 2003/09/26 19:42:54 thc
+% Changed \codeboxwidth from \textwidth to \linewidth so that the package
+% works in twocolumn mode.
+%
+% Revision 1.2 2003/06/19 14:51:17 thc
+% Fixed a bug that caused this package to interact badly with the
+% color package. Thanks to Janne Rinta-Mänty for reporting this bug
+% and suggesting the fix.
+%
+% Revision 1.1 2003/06/11 15:24:25 thc
+% Initial revision
+%
+
+% See the document "Using the clrscode Package in LaTeX 2e" for
+% examples.
+
+% Package for producing pseudocode in the style of Cormen, Leiserson,
+% Rivest, and Stein, Introduction to Algorithms, Second edition.
+
+% LIMITATION: This package works only if each procedure has at most 99
+% numbered lines of code.
+
+% Each pseudocode procedure is typeset within a codebox environment,
+% \begin{codebox}...\end{codebox}.
+
+% Normally, the first line within the codebox environment is a \Procname
+% command. The argument of the \Procname command is a math-mode
+% expression consisting of the procedure name and its parameters. The
+% name of the procedure itself goes within a \proc command. Example:
+% \Procname{$\proc{Matrix-Multiply}(A,B)$}
+% The \Procname command is optional.
+
+% To typeset the name of a procedure (e.g., Matrix-Multiply) in small
+% caps, use the \proc command:
+% \proc{Matrix-Multiply}
+
+% To typeset the name of a constant (e.g., nil) in small caps, use the
+% \const command:
+% \const{nil}
+
+% To typeset the name of an identifier (e.g., rank) in regular italics,
+% use the \id command:
+% \id{rank}
+
+% To typeset the name of a fixed function (e.g., sin) in roman, use the
+% \func command:
+% \func{sin}
+% (Note that several fixed functions, like sin, are already built into
+% LaTeX.)
+
+% The \proc, \const, \id, and \func commands not only use the correct
+% font, they also perform the important service of interpreting a dash
+% as a hyphen, rather than as a minus sign. These commands may be used
+% either in or out of math mode.
+
+% Other than the \Procname line, all lines begin with either \li (for a
+% numbered line) or \zi (for an unnumbered line). The following
+% commands are provided for typesetting keywords and handling automatic
+% indentation:
+
+% Loops: \For, \To, \By, \Downto, \Do, \While, \Repeat, \Until
+% Selection: \If, \Then, \Else, \ElseIf, \ElseNoIf
+% Jumps: \Return, \Error, \Goto
+% Comments: \Comment, \RComment
+% Indentation: \Indentmore, \Flushright
+
+% \label commands appearing in or after the first numbered line in a
+% codebox resolve to the number of the most recent numbered line.
+
+% \twodots produces the ".." notation used for subarrays.
+
+% Written for general distribution by Thomas H. Cormen, June 2003.
+
+% The author grants permission for anyone to use this macro package and
+% to distribute it unchanged without further restriction. If you choose
+% to modify this package, you must indicate that you have modified it
+% prior to your distributing it. I don't want to get bug reports about
+% changes that *you* have made!
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\ProvidesPackage{clrscode}[2007/03/29 v1.7 format pseudocode]
+\usepackage{latexsym} % needed for \Comment symbol
+
+% Commands for typesetting constants, procedure names, identifiers, and
+% fixed functions.
+\newcommand{\const}[1]{\textnormal{\scshape#1}}
+\newcommand{\proc}[1]{\textnormal{\scshape#1}}
+\newcommand{\text@hyphens}{\mathcode`\-=`\-\relax}
+\newcommand{\id}[1]{%
+ \ensuremath{\mathop{\mathit{\text@hyphens#1}}\nolimits}}
+\newcommand{\func}[1]{%
+ \ensuremath{\mathop{\text@hyphens\operator@font#1}\nolimits}}
+
+% Command for typesetting subarray ranges.
+\newcommand{\twodots}{\mathinner{\ldotp\ldotp}}
+
+% The codelinenumber counter counts the current line number.
+\newcounter{codelinenumber}
+
+% The indent counter keeps track of the current indentation level.
+\newcounter{indent}
+
+% The \iffirstcodeline command tells us whether we are about to
+% produce the first line other than the procedure declaration.
+\newif\iffirstcodeline\firstcodelinetrue
+
+% The \zeroli command makes it so that we're about to produce the
+% first line other than the procedure declaration.
+\newcommand{\zeroli}{\setcounter{codelinenumber}{0}%
+\setcounter{indent}{0}%
+\firstcodelinetrue}
+
+% \digitwidth gives the width of a single digit. All digits are the
+% same width. We'll need this amount to do the right thing for line
+% numbers.
+\newlength{\digitwidth}
+\settowidth{\digitwidth}{0}
+
+% The \li command bumps the counter, outputs it, and skips some space
+% A \label cmd for a given numbered line is allowed to appear after the
+% \\, as in
+% \li $x\gets y$ \label{li:assign-x}
+% But if \li merely set \@currentlabel in the usual way via
+% \refstepcounter, the value of \@currentlabel does not persist outside
+% the current cell. Solution: use an additional, global variable
+% \@lilabel.
+
+% THC: This next command is magic to me. I didn't write it.
+\def\@startline{\global\@curtabmar\@nxttabmar\relax
+ \global\@curtab\@curtabmar\setbox\@curline\hbox
+ {}\@startfield\strut}
+
+% \code@init is run at the beginning of a codebox environment.
+\def\code@init{%
+ \zeroli% producing the first line
+ \setlength{\tabbingsep}{1em}% distance between numbers and code
+ % Initialize \@lilabel to allow a pageref \label cmd at the beginning
+ % of the codebox
+ \global\let\@lilabel\@currentlabel
+ \def\@currentlabel{\@lilabel}%
+}
+
+% When we make a codebox, we save the code part into a box before
+% printing it. We do not actually print the code until we know how many
+% line numbers there are.
+\newsavebox{\savecode}
+
+% The \ifprocname command tells us whether this procedure has been
+% given a name yet.
+\newif\ifprocname\procnamefalse
+
+% Assume that the width of the codebox is the width of the text, minus
+% the width of 2 digits. We'll correct for that later.
+\newlength{\codeboxwidth}
+\setlength{\codeboxwidth}{\linewidth} % Thanks, David Etherington!
+\addtolength{\codeboxwidth}{-2\digitwidth}
+
+% The "codebox" environment produces an unbreakable section of code
+\newenvironment{codebox}{%
+\global\procnamefalse% this proc hasn't been given a name yet
+\code@init% set up for first line
+\begin{lrbox}{\savecode}% save the code into a box
+\begin{minipage}[t]{\codeboxwidth}% it'll be a minipage
+% Set up the tab stops
+\def\ifthentab{\textbf{if} \=\textbf{then} }%
+\begin{tabbing}%
+99\=\ \ifthentab \=\ifthentab \=\ifthentab \=\ifthentab \=\ifthentab
+ \=\textbf{if} \=\+\kill%
+}{%
+% Here's what's run at the end of a codebox environment. Start by
+% making sure that we have ended at indent level 0. Otherwise, print a
+% warning.
+\ifnum\value{indent}=0\else\typeout{Warning: Indentation ends at level \theindent\space in codebox on page \thepage.}\fi%
+\end{tabbing}\end{minipage}\end{lrbox}%
+\addtolength{\topsep}{0.5ex}% for the following trivlist
+\begin{trivlist}\item\parindent=0pt%
+% If there was a procedure name given, print it now but with a little
+% space below, and disallow a page break after the procedure name.
+\@nobreaktrue%
+\ifprocname\saveprocname\rule[-1.25ex]{0pt}{0pt}\\ \fi%
+% Put in the right amount of space, depending on whether we reached
+% double digits in the line numbers.
+\ifnum\value{codelinenumber}>9\hspace*{2\digitwidth}\else\hspace*{1\digitwidth}\fi%
+% Now print the code
+\usebox{\savecode}\end{trivlist}%
+\addtolength{\topsep}{-0.5ex}\global\procnamefalse}
+
+% Use the \Procname macro to give the name of the procedure.
+\newcommand{\Procname}[1]{\global\def\saveprocname{#1}\global\procnametrue}
+
+\newcounter{thisindent} % counter for recursive indenting code
+\newcommand{\Indent}{\setcounter{thisindent}{\value{indent}}\putindents}
+% \putindents is a recursive macro that indents a number of times given
+% by the counter thisindent.
+\newcommand{\putindents}{\ifnum\value{thisindent}>0\>\>\addtocounter{thisindent}{-1}\putindents\fi}
+
+% For typesetting any keyword in the main text.
+\newcommand{\kw}[1]{\textbf{#1}}
+
+% All of our favorite keywords.
+\newcommand{\For}{\textbf{for} }
+\newcommand{\To}{\textbf{to} }
+\newcommand{\By}{\textbf{by} }
+\newcommand{\Downto}{\textbf{downto} }
+\newcommand{\While}{\textbf{while} }
+\newcommand{\Repeat}{\textbf{repeat}\>\>\addtocounter{indent}{1}}
+\newcommand{\Until}{\kill\addtocounter{indent}{-1}\liprint\>\>\textbf{until}\hspace*{-0.7em}\'}
+\newcommand{\If}{\textbf{if} }
+\newcommand{\Then}{\>\textbf{then}\>\addtocounter{indent}{1}}
+\newcommand{\Else}{\kill\addtocounter{indent}{-1}\liprint\>\textbf{else}\>\addtocounter{indent}{1}}
+\newcommand{\End}{\addtocounter{indent}{-1}}
+\newcommand{\ElseIf}{\kill\addtocounter{indent}{-1}\liprint\textbf{elseif} }
+\newcommand{\ElseNoIf}{\kill\addtocounter{indent}{-1}\liprint\textbf{else} \addtocounter{indent}{1}}
+\newcommand{\Do}{\>\>\textbf{do}\hspace*{-0.7em}\'\addtocounter{indent}{1}}
+\newcommand{\Return}{\textbf{return} }
+\newcommand{\Comment}{$\hspace*{-0.075em}\rhd$ }
+\newcommand{\RComment}{\`\Comment}
+\newcommand{\Goto}{\textbf{goto} }
+\newcommand{\Error}{\textbf{error} } % optionally followed by string argument
+
+% Indent the next line one level more
+\newcommand{\Indentmore}{\addtocounter{indent}{1}}
+
+% Make the next line be flush against the right margin.
+\newcommand{\Flushright}{\`}
+
+\newif\ifnumberedline
+\numberedlinetrue
+
+% The \li command starts a new numbered line.
+\newcommand{\li}{\global\numberedlinetrue%
+\iffirstcodeline\global\firstcodelinefalse\else\\ \fi
+\stepcounter{codelinenumber}%
+\liprint}
+
+% The \lispace command starts a new numbered line with a little extra
+% space above, given by the argument.
+\newcommand{\lispace}[1]{\iffirstcodeline\global\firstcodelinefalse\else\\[#1] \fi
+\stepcounter{codelinenumber}%
+\liprint}
+
+% \liprint actually prints the line number and sets up the indentation.
+\newcommand{\liprint}{\protected@xdef\@lilabel{\thecodelinenumber}%
+\ifnumberedline\thecodelinenumber\fi\'\Indent%
+}
+
+\providecommand{\numref}[1]{%
+ \@ifundefined{r@#1}{000}{%
+ \expandafter\expandafter\expandafter\@firstoftwo
+ \csname r@#1\endcsname
+ }%
+}
+
+% \setlinenumber sets the line number to its argument
+\newcommand{\setlinenumber}[1]{\setcounter{codelinenumber}{\numref{#1}}%
+\addtocounter{codelinenumber}{-1}}
+% \setlinenumberplus sets the line number to its first argument plus its
+% second argument.
+\newcommand{\setlinenumberplus}[2]{\setcounter{codelinenumber}{\numref{#1}}%
+\addtocounter{codelinenumber}{-1}\addtocounter{codelinenumber}{#2}}
+
+% The \zi command starts a new unnumbered line.
+\newcommand{\zi}{\global\numberedlinefalse%
+\iffirstcodeline\global\firstcodelinefalse\else\\ \fi
+\liprint}
+
+\endinput
diff --git a/macros/latex/contrib/clrscode/clrscode.tex b/macros/latex/contrib/clrscode/clrscode.tex
new file mode 100644
index 0000000000..e2bb057247
--- /dev/null
+++ b/macros/latex/contrib/clrscode/clrscode.tex
@@ -0,0 +1,744 @@
+% $Id$
+% $Log$
+
+\documentclass[11pt,mtbold]{article}
+\usepackage{mathtime}
+\usepackage{clrscode}
+\input{page}
+
+\newcommand{\subheading}[1]{\subsubsection*{#1}}
+\newcommand{\clrscode}{\texttt{clrscode}}
+\newcommand{\Codebox}{\texttt{codebox}}
+
+\begin{document}
+
+\title{Using the \clrscode{} Package in \LaTeXe}
+\author{Thomas H. Cormen \\ thc@cs.dartmouth.edu}
+\date{June 11, 2003}
+
+\maketitle
+
+\section{Introduction}
+\label{sec:intro}
+
+This document describes how to use the \clrscode{} package in
+\LaTeXe{} to typeset pseudocode in the style of \textit{Introduction
+to Algorithms}, Second edition, by Cormen, Leiserson, Rivest, and
+Stein (CLRS) \cite{CLRS01}. You use the commands in the same way we
+did in writing CLRS, and your output will look just like the
+pseudocode in the text.
+
+\section{Setup}
+\label{sec:setup}
+
+To get the \clrscode{} package, download
+http://www.cs.dartmouth.edu/\~{ }thc/clrscode/clrscode.sty .
+To use the package, include the following line in your source file:
+
+{\small
+\begin{verbatim}
+\usepackage{clrscode}
+\end{verbatim}
+}
+
+\noindent The \clrscode{} package itself includes the line
+
+{\small
+\begin{verbatim}
+\usepackage{latexsym}
+\end{verbatim}
+}
+
+\noindent This line is necessary in order to get the character $\rhd$
+for comments in pseudocode. Therefore, you will need to have the
+\texttt{latexsym} package installed and available on your system.
+
+\section{Typesetting names}
+\label{sec:names}
+
+Pseudocode in CLRS uses four types of names: identifiers, procedures,
+constants, and fixed functions. We provide commands \verb`\id`,
+\verb`\proc`, \verb`\const`, and \verb`\func` for these names. Each
+of these commands takes one argument, which is the name being typeset.
+These commands work both in and out of math mode. When used in math
+mode, and when the name given as an argument contains a dash, the dash
+is typeset as a hyphen rather than as a minus sign.
+
+\begin{description}
+
+\item[Identifiers:] Identifiers are used for variable and attribute
+names. When a variable name is just a single letter, e.g., the
+identifier $j$ in line~2 of \proc{Insertion-Sort} on page~17, we just
+typeset it in math mode: \verb`$j$`.
+
+Identifiers consisting of two or more letters, e.g., the attribute
+\id{length} in the same line of \proc{Insertion-Sort}, should not be
+typeset in this way. (See page~51 of Lamport \cite{Lamport93}.)
+Although \LaTeXe{} provides the \verb`\mathit` command for typesetting
+multiletter identifiers, we use our \verb`\id` command instead:
+\verb`\id{length}`. We recommend that you use it, too. Since the
+\verb`\id` command may be used both in and out of math mode, the source
+text
+
+{\small
+\begin{verbatim}
+We use the \id{length} attribute to denote the length of an array,
+e.g., $\id{length}[A]$.
+\end{verbatim}
+}
+
+\noindent will produce
+\begin{quote}
+We use the \id{length} attribute to denote the length of an array,
+e.g., $\id{length}[A]$.
+\end{quote}
+
+\sloppy
+
+To see how a dash turns into a hyphen, consider line~3
+of \proc{Max-Heapify} on page~130. Its source contains the text
+\verb`$l \leq \id{heap-size}[A]$`, which typesets as $l \leq
+\id{heap-size}[A]$. Using \verb`$l \leq \mathit{heap-size}[A]$` would
+produce $l \leq \mathit{heap-size}[A]$, with a minus sign rather than
+a hyphen in the identifier.
+
+\fussy
+
+\item[Procedures:] For procedure names, use the \verb`\proc` command.
+It typesets procedure names in small caps, and dashes (which occur
+frequently in our procedure names) are typeset as hyphens. Thus, the
+source \verb`\proc{Insertion-Sort}` produces \proc{Insertion-Sort}.
+Since you can use the \verb`\proc` command both in and out of math mode,
+the source text
+
+{\small
+\begin{verbatim}
+We call \proc{Insertion-Sort} with an array $A$, so that the
+call is $\proc{Insertion-Sort}(A)$.
+\end{verbatim}
+}
+
+\noindent will produce
+\begin{quote}
+We call \proc{Insertion-Sort} with an array $A$, so that the
+call is $\proc{Insertion-Sort}(A)$.
+\end{quote}
+
+\item[Constants:] We typeset constants like \const{nil}, \const{true},
+and \const{red} in small caps with the \verb`\const` command, e.g.,
+\verb`\const{nil}`, \verb`\const{true}`, and \verb`\const{red}`. I
+don't think that any of our constants have dashes in them, but the
+\verb`\const` command would typeset a dash within a constant name as a
+hyphen, so that \verb`$\const{red-and-black}$` will produce
+$\const{red-and-black}$.
+
+\item[Fixed functions:] We typeset the names of fixed functions in
+plain old roman with the \verb`\func` command, e.g., \func{level} and
+\func{out-degree}. By a ``fixed function,'' we mean a function that
+is a specific, given function. For example, the $\sin$ function is
+typically typeset in roman; $\sin x$ looks right, but wouldn't
+$\id{sin} x$ look strange? Yet, on page~42, $\Theta(g(n))$ looks
+right, but $\Theta(\textrm{g}(n))$ would look wrong, since $g$ is a
+variable that stands for any one of a number of functions.
+
+As with the other commands for names, a dash within a function name will
+typeset as a hyphen, so that \verb`$\func{out-degree}$` will produce
+$\func{out-degree}$ rather than $\textrm{out}-\textrm{degree}$. Note
+that \LaTeXe{} provides commands for many fixed functions, such as
+$\sin$ and $\log$; Table 3.9 on page~44 of~\cite{Lamport93} lists
+these ``log-like'' functions.
+
+\end{description}
+
+There is one other command that doesn't really fit anywhere else, so
+I'll mention it here. We denote subarrays with the ``$\twodots$''
+notation, which is produced by the \verb`\twodots` command. Thus, the
+source text \verb`$A[1 \twodots j-1]$` will produce $A[1 \twodots
+j-1]$. The \verb`\twodots` command must be used in math mode.
+
+\section{The \Codebox{} environment}
+\label{sec:codebox}
+
+We typeset pseudocode by putting it in a \Codebox{} environment. A
+\Codebox{} is a section of code that will not break across pages (I
+hope).
+
+\subheading{Contents of a \Codebox{}}
+
+Each procedure should go in a separate \Codebox{}, even if you have
+multiple procedures appearing consecutively. The only possible reason
+I can think of to put more than one procedure in a single \Codebox{}
+is to ensure that the procedures appear on the same page. If you
+really need your procedures to appear on the same page, there are
+other means in \LaTeXe, such as the \texttt{minipage} environment,
+that you can use. Moreover, if you have written your procedures so
+that they have to appear on the same page, you should probably be
+asking yourself whether they are too interdependent.
+
+The typical structure within a \Codebox{} is as follows. Usually, the
+first line is the name of a procedure, along with a list of
+parameters. (Not all \Codebox{}es include procedure names; for
+example, see the pseudocode near the bottom of page~306 of CLRS\@.)
+After the line containing the procedure name comes one or more lines
+of code, usually numbered. Some of the lines may be unnumbered, being
+continuations of previous lines. In rare cases, when there is just
+one line of code per procedure, we don't bother numbering the line;
+see the \proc{Parent}, \proc{Left}, and \proc{Right} procedures on
+page~128 for example. Lines are usually numbered starting from~1, but
+again there are exceptions, such as the pseudocode near the bottom of
+page~306.
+
+\subheading{Using \texttt{$\backslash$Procname} to name the procedure}
+
+The \verb`\Procname` command specifies the name of the procedure. It
+takes as a parameter the procedure name and parameters, typically all
+in math mode. \verb`\Procname` makes its argument flush left against
+the margin, and it leaves a little bit of extra space below the line.
+For example, here is how we typeset the \proc{Insertion-Sort}
+procedure on page~17:
+
+{\small
+\begin{verbatim}
+\begin{codebox}
+\Procname{$\proc{Insertion-Sort}(A)$}
+\li \For $j \gets 2$ \To $\id{length}[A]$
+\li \Do
+ $\id{key} \gets A[j]$
+\li \Comment Insert $A[j]$ into the sorted sequence
+ $A[1 \twodots j-1]$.
+\li $i \gets j-1$
+\li \While $i > 0$ and $A[i] > \id{key}$
+\li \Do
+ $A[i+1] \gets A[i]$
+\li $i \gets i-1$
+ \End
+\li $A[i+1] \gets \id{key}$
+ \End
+\end{codebox}
+\end{verbatim}
+}
+
+\subheading{Using \texttt{$\backslash$li} and \texttt{$\backslash$zi}
+to start new lines}
+
+To start a new, numbered line, use the \verb`\li` command. To start a
+new, \emph{un}numbered line, use the \verb`\zi` command. Note that
+since a \Codebox{} is not like the \verb`verbatim` environment, the
+line breaks within the source text do not correspond to the line
+breaks in the typeset output.
+
+\subheading{Tabs}
+
+I find that it is best to set the tab stops to every 4 characters when
+typing in and displaying pseudocode source with the \clrscode{}
+package. I use emacs, and to get the tabs set up the way I want them,
+my \mbox{\texttt{tex-mode.el}} file includes the line
+\verb`(setq tab-width 4)`. For reasons I do not understand, sometimes
+emacs ``forgets'' this setting, and I have to do a little friendly
+persuasion.
+
+A \Codebox{} environment has a \verb`tabbing` environment within it.
+The tab stops come in pairs, in that each pair of tab stops gives one
+level of indentation. Tab stops are paired up so that when we typeset
+the keywords \kw{then} and \kw{else}, they have the correct vertical
+alignment. In other words, within each pair of tab stops, the first
+stop is where \kw{then} and \kw{else} begin, and the second stop
+completes a full level of indentation. For the most part, you won't
+need to be concerned with tabs. The primary exception is when you
+want to include a comment at the end of a line of pseudocode, and
+especially when you want to include comments after several lines and
+you want the comments to vertically align. Note that the
+\verb`tabbing` environment within a codebox has nothing to do with
+tabs that you enter in your source code; when you press the TAB key,
+that's the same as pressing the space bar in the eyes of \LaTeXe{}.
+
+\subheading{Commands for keywords}
+
+As you can see from the source for \proc{Insertion-Sort}, there are
+commands \verb`\For`, \verb`\Do`, and \verb`\While` that produce the
+keywords \kw{for}, \kw{do}, and \kw{while}. \verb`\Do` and some other
+commands also affect indentation.
+
+Sometimes you want to include a keyword in the main text, as I have
+done in several places in this document. Use the \verb`\kw` command
+to do so. For example, to produce a sentence that appeared two
+paragraphs ago, I typed in the following:
+
+{\small
+\begin{verbatim}
+Tab stops are paired up so that when we typeset the keywords \kw{then}
+and \kw{else}, they have the correct vertical alignment.
+\end{verbatim}
+}
+
+The following commands simply produce their corresponding keywords,
+typeset in boldface: \verb`\For`, \verb`\To`, \verb`\Downto`,
+\verb`\By`, \verb`\While`, \verb`\If`, \verb`\Return`, \verb`\Goto`,
+and \verb`\Error`. Although you could achieve the same effect with
+the \verb`\kw` command (e.g., \verb`\kw{for}` instead of \verb`\For`),
+you will find it easier and more readable to use the above commands.
+The \verb`\Comment` command simply produces the comment symbol~$\rhd$.
+None of the above commands affects indentation.
+
+In \kw{for} loops and \kw{while} loops, the important commands are
+\verb`\Do` and \verb`\End`. \verb`\Do` produces the keyword \kw{do},
+and it also increments the indentation level. \verb`\End` simply
+decrements the indentation level, and it is the way to end any
+\kw{for} or \kw{while} loop or otherwise decrement the indentation
+level.
+
+As you can see from the above example, I like to place each \verb`\Do`
+and \verb`\End` on its own line. You can of course format your source
+text as you like, but I find that the way I format pseudocode makes it
+easy to match up \verb`\Do`-\verb`\End` pairs.
+
+We also use \verb`\End` to terminate an \kw{if}-\kw{then} or
+\kw{if}-\kw{then}-\kw{else} construct. For an example of
+\kw{if}-\kw{then}, here's the \proc{Merge-Sort} procedure on page~32:
+
+\newpage
+
+{\small
+\begin{verbatim}
+\begin{codebox}
+\Procname{$\proc{Merge-Sort}(A, p, r)$}
+\li \If $p < r$
+\li \Then
+ $q \gets \floor{(p + r) / 2}$
+\li $\proc{Merge-Sort}(A, p, q)$
+\li $\proc{Merge-Sort}(A, q+1, r)$
+\li $\proc{Merge}(A, p, q, r)$
+ \End
+\end{codebox}
+\end{verbatim}
+}
+
+\noindent For a more complicated example, using
+\kw{if}-\kw{then}-\kw{else}, here's the \proc{Tree-Insert} procedure
+on page~261:
+
+{\footnotesize
+\begin{verbatim}
+\begin{codebox}
+\Procname{$\proc{Tree-Insert}(T,z)$}
+\li $y \gets \const{nil}$
+\li $x \gets \id{root}[T]$
+\li \While $x \neq \const{nil}$
+\li \Do
+ $y \gets x$
+\li \If $\id{key}[z] < \id{key}[x]$
+\li \Then $x \gets \id{left}[x]$
+\li \Else $x \gets \id{right}[x]$
+ \End
+ \End
+\li $p[z] \gets y$
+\li \If $y = \const{nil}$
+\li \Then
+ $\id{root}[T] \gets z$\>\>\>\>\>\>\>\>\Comment Tree $T$ was empty
+\li \Else
+ \If $\id{key}[z] <\ id{key}[y]$
+\li \Then $\id{left}[y]\ gets z$
+\li \Else $\id{right}[y] \gets z$
+ \End
+ \End
+\end{codebox}
+\end{verbatim}
+}
+
+\noindent As you can see, I like to line up the \verb`\End` commands
+under the \verb`\Then` and \verb`\Else` commands. I could just as
+easily have chosen to line up \verb`\End` under the \verb`\If` command
+instead. I also sometimes elect to put the ``then'' or ``else'' code
+on the same source line as the \verb`\Then` or \verb`\Else` command,
+especially when that code is short.
+
+The \proc{Tree-Insert} example also shows how we put a comment on the
+same line as code. Via the tab command \verb`\>`, we explicitly tab
+to where we want the comment to begin and then use the \verb`\Comment`
+command to produce the comment symbol. When there are several lines
+with comments, you probably want them to align vertically. I just add
+tab characters, using a trial-and-error approach, until I am pleased
+with the result. For example, here's how we produced the
+\proc{KMP-Matcher} procedure on page~926:
+
+\newpage
+
+{\footnotesize
+\begin{verbatim}
+\begin{codebox}
+\Procname{$\proc{KMP-Matcher}(T,P)$}
+\li $n \gets \id{length}[T]$
+\li $m \gets \id{length}[P]$
+\li $\pi \gets \proc{Compute-Prefix-Function}(P)$
+\li $q \gets 0$\>\>\>\>\>\>\>\>\>\>\Comment Number of characters matched.
+\li \For $i \gets 1$ \To $n$\>\>\>\>\>\>\>\>\>\>\Comment
+ Scan the text from left to right.
+\li \Do
+ \While $q > 0$ and $\Px{q+1} \neq \Tx{i}$
+\li \Do $q \gets \pi[q]$\>\>\>\>\>\>\Comment Next character does not match.
+ \End
+\li \If $\Px{q+1} = \Tx{i}$
+\li \Then $q \gets q+1$\>\>\>\>\>\>\Comment Next character matches.
+ \End
+\li \If $q = m$\>\>\>\>\>\>\>\>\Comment Is all of $P$ matched?
+\li \Then
+ print ``Pattern occurs with shift'' $i-m$
+\li $q \gets \pi[q]$\>\>\>\>\>\>\Comment Look for the next match.
+ \End
+ \End
+\end{codebox}
+\end{verbatim}
+}
+
+\noindent All six comments align nicely.
+
+For a \kw{repeat} loop, use the \verb`\Repeat` and \verb`\Until`
+commands, as in the \proc{Hash-Insert} procedure on page~238:
+
+{\small
+\begin{verbatim}
+\begin{codebox}
+\Procname{$\proc{Hash-Insert}(T,k)$}
+\li $i \gets 0$
+\li \Repeat
+ $j \gets h(k,i)$
+\li \If $T[j] = \const{nil}$
+\li \Then
+ $T[j]\gets k$
+\li \Return $j$
+\li \Else
+ $i \gets i+1$
+ \End
+\li \Until $i = m$
+\li \Error ``hash table overflow''
+\end{codebox}
+\end{verbatim}
+}
+
+\noindent Note that the \verb`\Until` command has an implied
+\verb`\End`.
+
+Sometimes, you need more complicated ``\kw{if}-ladders'' than you can
+get from the \verb`\Then` and \verb`\Else` commands. The
+\proc{Randomized-Select} procedure on page~186 provides an example,
+and it uses the \verb`\ElseIf` and \verb`\ElseNoIf` commands:
+
+\newpage
+
+{\small
+\begin{verbatim}
+\begin{codebox}
+\Procname{$\proc{Randomized-Select}(A, p, r, i)$}
+\li \If $p = r$
+\li \Then \Return $A[p]$
+ \End
+\li $q \gets \proc{Randomized-Partition}(A, p, r)$
+\li $k \gets q - p +1$
+\li \If $i = k$\>\>\>\>\Comment the pivot value is the answer
+\li \Then \Return $A[q]$
+\li \ElseIf $i < k$
+\li \Then \Return $\proc{Randomized-Select}(A, p, q-1, i)$
+\li \ElseNoIf \Return $\proc{Randomized-Select}(A, q+1, r, i-k)$
+ \End
+\end{codebox}
+\end{verbatim}
+}
+
+\noindent For an \kw{if}-ladder, use \verb`\Then` for the first case,
+\verb`\ElseNoIf` for the last case, and \verb`\ElseIf` for all
+intermediate cases. An \kw{if}-ladder is terminated by \verb`\End`.
+As another example, here is the \proc{Segments-Intersect} procedure on
+page~937:
+
+{\small
+\begin{verbatim}
+\begin{codebox}
+\Procname{$\proc{Segments-Intersect}(p_1, p_2, p_3, p_4)$}
+\li $d_1 \gets \proc{Direction}(p_3, p_4, p_1)$
+\li $d_2 \gets \proc{Direction}(p_3, p_4, p_2)$
+\li $d_3 \gets \proc{Direction}(p_1, p_2, p_3)$
+\li $d_4 \gets \proc{Direction}(p_1, p_2, p_4)$
+\li \If $((d_1 > 0 \mbox{ and } d_2 < 0) \mbox{ or }
+ (d_1 < 0 \mbox{ and } d_2 > 0))$ and
+ \Indentmore
+\zi $((d_3 > 0 \mbox{ and } d_4 < 0) \mbox{ or }
+ (d_3 < 0 \mbox{ and } d_4 > 0))$
+ \End
+\li \Then \Return \const{true}
+\li \ElseIf $d_1 = 0$ and $\proc{On-Segment}(p_3, p_4, p_1)$
+\li \Then \Return \const{true}
+\li \ElseIf $d_2 = 0$ and $\proc{On-Segment}(p_3, p_4, p_2)$
+\li \Then \Return \const{true}
+\li \ElseIf $d_3 = 0$ and $\proc{On-Segment}(p_1, p_2, p_3)$
+\li \Then \Return \const{true}
+\li \ElseIf $d_4 = 0$ and $\proc{On-Segment}(p_1, p_2, p_4)$
+\li \Then \Return \const{true}
+\li \ElseNoIf \Return \const{false}
+ \End
+\end{codebox}
+\end{verbatim}
+}
+
+This example also shows our first use of an unnumbered line: the
+second half of the tests on line~5. We use \verb`\zi` to indicate
+that we're starting an unnumbered line.
+
+\subheading{Indentation}
+
+We also wish to indent the unnumbered line after line~5 by one level
+more than the line above it. We do so with the \verb`\Indentmore`
+command. The \verb`\End` command following the indented line
+decrements the indentation level back to what it was prior to the
+\verb`\Indentmore`. If I had wanted to indent the line by two levels,
+I would have used two \verb`\Indentmore` commands before the line and
+two \verb`\End` commands afterward. (Recall that \verb`\End` simply
+decrements the indentation level.)
+
+Upon seeing the \verb`\end{codebox}` command, the \Codebox{}
+environment checks that the indentation level is back to where it was
+when it started, namely an indentation level of~0. If it is not, you
+will get a warning message like the following:
+
+{\small
+\begin{verbatim}
+Warning: Indentation ends at level 1 in codebox on page 1.
+\end{verbatim}
+}
+
+\noindent This message would indicate that there is one missing
+\verb`\End` command. On the other hand, you might have one too many
+\verb`\End` commands, in which case you would get
+
+{\small
+\begin{verbatim}
+Warning: Indentation ends at level -1 in codebox on page 1.
+\end{verbatim}
+}
+
+\subheading{Right justification}
+
+The final two commands, \verb`\RComment` and \verb`\Flushright`, are
+infrequently used and pertain to right justification.
+\verb`\RComment` produces a comment that is flush against the right
+margin. For example, here is how we typeset the
+\proc{Binomial-Heap-Union} procedure on page~463:
+
+\newpage
+
+{\footnotesize
+\begin{verbatim}
+\begin{codebox}
+\Procname{$\proc{Binomial-Heap-Union}(H_1,H_2)$}
+\li $H \gets \proc{Make-Binomial-Heap}()$
+\li $\id{head}[H] \gets \proc{Binomial-Heap-Merge}(H_1,H_2)$
+\li free the objects $H_1$ and $H_2$ but not the lists they point to
+\li \If $\id{head}[H] = \const{nil}$
+\li \Then \Return $H$
+ \End
+\li $\id{prev-x} \gets \const{nil}$
+\li $x \gets \id{head}[H]$
+\li $\id{next-x} \gets \id{sibling}[x]$
+\li \While $\id{next-x} \neq \const{nil}$
+\li \Do
+ \If $(\id{degree}[x] \neq \id{degree}[\id{next-x}])$ or
+\zi \Flushright $(\id{sibling}[\id{next-x}] \neq \const{nil}$
+ and $\id{degree}[\id{sibling}[\id{next-x}]] = \id{degree}[x])$
+\li \Then
+ $\id{prev-x} \gets x$
+ \RComment Cases 1 and 2
+\li $x \gets \id{next-x}$
+ \RComment Cases 1 and 2
+\li \Else
+ \If $\id{key}[x] \leq \id{key}[\id{next-x}]$
+\li \Then
+ $\id{sibling}[x] \gets \id{sibling}[\id{next-x}]$
+ \RComment Case 3
+\li $\proc{Binomial-Link}(\id{next-x},x)$
+ \RComment Case 3
+\li \Else
+ \If $\id{prev-x} = \const{nil}$
+ \RComment Case 4
+\li \Then $\id{head}[H] \gets \id{next-x}$
+ \RComment Case 4
+\li \Else $\id{sibling}[\id{prev-x}] \gets
+ \id{next-x}$
+ \RComment Case 4
+ \End
+\li $\proc{Binomial-Link}(x,\id{next-x})$
+ \RComment Case 4
+\li $x \gets \id{next-x}$
+ \RComment Case 4
+ \End
+ \End
+\li $\id{next-x} \gets \id{sibling}[x]$
+ \End
+\li \Return $H$
+\end{codebox}
+\end{verbatim}
+}
+
+\noindent This procedure is also the only place in CLRS in which we
+used the \verb`\Flushright` command. It puts the unnumbered line
+following line~10 flush against the right margin.
+
+\subheading{Referencing line numbers}
+
+In the source files for CLRS, there are no absolute references to line
+numbers. We use \emph{only} symbolic references. The \Codebox{}
+environment is set up to allow you to place \verb`\label` commands on
+lines of pseudocode and then reference these labels. The references
+will resolve to the line numbers. Our convention is that any label
+for a line number begins with \verb`\li:`, but you can name the labels
+any way that you like.
+
+For example, here's how we \emph{really} wrote the
+\proc{Insertion-Sort} procedure on page~17:
+
+{\small
+\begin{verbatim}
+\begin{codebox}
+\Procname{$\proc{Insertion-Sort}(A)$}
+\li \For $j \gets 2$ \To $\id{length}[A]$
+ \label{li:ins-sort-for}
+\li \Do $\id{key} \gets A[j]$ \label{li:ins-sort-pick}
+ \label{li:ins-sort-for-body-begin}
+\li \Comment Insert $A[j]$ into the sorted sequence
+ $A[1 \twodots j-1]$.
+\li $i \gets j-1$ \label{li:ins-sort-find-begin}
+\li \While $i > 0$ and $A[i] > \id{key}$
+ \label{li:ins-sort-while}
+\li \Do
+ $A[i+1] \gets A[i]$ \label{li:ins-sort-while-begin}
+\li $i \gets i-1$ \label{li:ins-sort-find-end}
+ \label{li:ins-sort-while-end}
+ \End
+\li $A[i+1] \gets \id{key}$ \label{li:ins-sort-ins}
+ \label{li:ins-sort-for-body-end}
+ \End
+\end{codebox}
+\end{verbatim}
+}
+
+\noindent Note that any line may have multiple labels. As an example
+of referencing these labels, here's the beginning of the first item
+under ``Pseudocode conventions'' on page~19:
+
+{\small
+\begin{verbatim}
+\item For example, the body of the \kw{for} loop that begins on
+line~\ref{li:ins-sort-for} consists of lines
+\ref{li:ins-sort-for-body-begin}--\ref{li:ins-sort-for-body-end},
+and the body of the \kw{while} loop that begins on
+line~\ref{li:ins-sort-while} contains lines
+\ref{li:ins-sort-while-begin}--\ref{li:ins-sort-while-end} but
+not line~\ref{li:ins-sort-for-body-end}.
+\end{verbatim}
+}
+
+\subheading{Setting line numbers}
+
+On rare occasions, we needed to start line numbers somewhere other
+than~1. Use the \verb`setlinenumber` command to set the next line
+number. For example, in Exercise~24.2-2 on page~594, we want the line
+number to be the same as a line number within the
+\proc{Dag-Shortest-Paths} procedure on page~592. Here's the source
+for the exercise:
+
+{\small
+\begin{verbatim}
+Suppose we change line~\ref{li:dag-sp-loop-begin} of
+\proc{Dag-Shortest-Paths} to read
+
+\begin{codebox}
+\setlinenumber{li:dag-sp-loop-begin}
+\li \For the first $\card{V}-1$ vertices, taken in topologically sorted order
+\end{codebox}
+Show that the procedure would remain correct.
+\end{verbatim}
+}
+
+\noindent The \proc{Dag-Shortest-Paths} procedure is
+
+{\small
+\begin{verbatim}
+\begin{codebox}
+\Procname{$\proc{Dag-Shortest-Paths}(G,w,s)$}
+\li topologically sort the vertices of $G$ \label{li:dag-sp-topo-sort}
+\li $\proc{Initialize-Single-Source}(G,s)$ \label{li:dag-sp-init}
+\li \For each vertex $u$, taken in topologically sorted order
+ \label{li:dag-sp-loop-begin}
+\li \Do
+ \For each vertex $v \in \id{Adj}[u]$
+ \label{li:dag-sp-inner-begin}
+\li \Do $\proc{Relax}(u,v,w)$ \label{li:dag-sp-loop-end}
+ \End
+ \End
+\end{codebox}
+\end{verbatim}
+}
+
+Even more rarely (just once, in fact), we needed to set a line number
+to be some other line number plus an offset. That was in the two
+lines of pseudocode near the bottom of page~306, where the first line
+number had to be one greater than the number of the last line of
+\proc{Left-Rotate} on page~278. Use the \verb`setlinenumberplus`
+command:
+
+{\footnotesize
+\begin{verbatim}
+\begin{codebox}
+\setlinenumberplus{li:left-rot-parent}{1}
+\li $\id{size}[y] \gets \id{size}[x]$
+\li $\id{size}[x] \gets \id{size}[\id{left}[x]] + \id{size}[\id{right}[x]] + 1$
+\end{codebox}
+\end{verbatim}
+}
+
+\noindent Here, the last line of \proc{Left-Rotate} has
+\verb`\label{li:left-rot-parent}`.
+
+\section{Reporting bugs}
+\label{sec:bugs}
+
+If you find errors in the \clrscode{} package, please send me email
+(thc@cs.dartmouth.edu). It would be best if your message included
+everything I would require to elicit the error myself.
+
+The \texttt{clrscode.sty} file contains the following disclaimer:
+
+{\small
+\begin{verbatim}
+% Written for general distribution by Thomas H. Cormen, June 2003.
+
+% The author grants permission for anyone to use this macro package and
+% to distribute it unchanged without further restriction. If you choose
+% to modify this package, you must indicate that you have modified it
+% prior to your distributing it. I don't want to get bug reports about
+% changes that *you* have made!
+\end{verbatim}
+}
+
+\noindent I have enough trouble keeping up with my own bugs; I don't
+want to hear about bugs that others have introduced in the package!
+
+\section{Revision history}
+
+\begin{itemize}
+
+\item 11 June 2003. Initial revision of document and code.
+
+\end{itemize}
+
+\begin{thebibliography}{9}
+
+\bibitem{CLRS01} Thomas H. Cormen, Charles E. Leiserson, Ronald L.
+Rivest, and Clifford Stein. \textit{Introduction to Algorithms},
+second edition. The MIT Press and McGraw-Hill, 2001.
+
+\bibitem{Lamport93} Leslie Lamport. \textit{\LaTeX: A Document
+Preparation System User's Guide and Reference Manual}.
+Addison-Wesley, 1993.
+
+\end{thebibliography}
+
+\end{document}
diff --git a/macros/latex/contrib/clrscode/page.tex b/macros/latex/contrib/clrscode/page.tex
new file mode 100644
index 0000000000..de6c87bfc8
--- /dev/null
+++ b/macros/latex/contrib/clrscode/page.tex
@@ -0,0 +1,18 @@
+\setlength{\oddsidemargin}{0in}
+\setlength{\evensidemargin}{0in}
+\setlength{\textwidth}{6.5in}
+\setlength{\topmargin}{0in}
+\setlength{\textheight}{8.5in}
+\setlength{\headheight}{0pt}
+\setlength{\headsep}{0pt}
+
+\setcounter{topnumber}{3}%
+\def\topfraction{.7}%
+\setcounter{bottomnumber}{1}
+\def\bottomfraction{.3}
+\setcounter{totalnumber}{5}%
+\def\textfraction{.1}% was .2
+\def\floatpagefraction{.7}% was .7
+\setcounter{dbltopnumber}{2}
+\def\dbltopfraction{.7}
+\def\dblfloatpagefraction{.5}