diff options
author | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
commit | e0c6872cf40896c7be36b11dcc744620f10adf1d (patch) | |
tree | 60335e10d2f4354b0674ec22d7b53f0f8abee672 /macros/latex/contrib/clrscode3e |
Initial commit
Diffstat (limited to 'macros/latex/contrib/clrscode3e')
-rw-r--r-- | macros/latex/contrib/clrscode3e/README | 3 | ||||
-rw-r--r-- | macros/latex/contrib/clrscode3e/clrscode3e.pdf | bin | 0 -> 76665 bytes | |||
-rw-r--r-- | macros/latex/contrib/clrscode3e/clrscode3e.sty | 343 | ||||
-rw-r--r-- | macros/latex/contrib/clrscode3e/clrscode3e.tex | 999 | ||||
-rw-r--r-- | macros/latex/contrib/clrscode3e/page.tex | 18 |
5 files changed, 1363 insertions, 0 deletions
diff --git a/macros/latex/contrib/clrscode3e/README b/macros/latex/contrib/clrscode3e/README new file mode 100644 index 0000000000..f0572c09cf --- /dev/null +++ b/macros/latex/contrib/clrscode3e/README @@ -0,0 +1,3 @@ +Use this package to typeset pseudocode in the style of Introduction to Algorithms, third edition, by Cormen, Leiserson, Rivest, and Stein. + +This package is distributed under the LaTeX Project Public License. diff --git a/macros/latex/contrib/clrscode3e/clrscode3e.pdf b/macros/latex/contrib/clrscode3e/clrscode3e.pdf Binary files differnew file mode 100644 index 0000000000..2c4d86b3c6 --- /dev/null +++ b/macros/latex/contrib/clrscode3e/clrscode3e.pdf diff --git a/macros/latex/contrib/clrscode3e/clrscode3e.sty b/macros/latex/contrib/clrscode3e/clrscode3e.sty new file mode 100644 index 0000000000..8157a009d8 --- /dev/null +++ b/macros/latex/contrib/clrscode3e/clrscode3e.sty @@ -0,0 +1,343 @@ +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +% clrscode3e.sty + +% See the document "Using the clrscode3e Package in LaTeX 2e" for +% examples. + +% Package for producing pseudocode in the style of Cormen, Leiserson, +% Rivest, and Stein, Introduction to Algorithms, Third 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. + +% For attributes, use the various forms of the \attrib commands. + +% 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 +% Multithreading: \Spawn, \Sync, \Parfor +% Comments: \Comment, \RComment, \CommentSymbol +% Indentation: \Indentmore, \Startalign, \Stopalign + +% \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, March 2009. + +% 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{clrscode3e} +\RequirePackage{graphics} % needed for \scalebox command + +% The \useregularv command is because we used a different lowercase v +% in math mode in the book. Most users of the clrscode3e package will +% use the standard lowercase v in math mode, and so the \useregularv +% command is a no-op for them. +\ifdefined\useregularv\else\newcommand{\useregularv}{}\fi + +% 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{\func}[1]{% + \ensuremath{{\useregularv\mathop{\text@hyphens\operator@font#1}\nolimits}}} +\newcommand{\id}[1]{% + \ensuremath{\mathit{\text@hyphens#1}}} + +% Commands for typesetting object attributes. All of these commands +% may be used either in or out of math mode. + +% Definitions: +% An i-string is a string that you would use in an \id command, +% typically one or more non-Greek letters, numerals, or dashes. +% An x-string is a string that you would not use in an \id command, +% typically because it has a subscript or one or more Greek letters. +% A single non-Greek letter can be either an i-string or an x-string. + +% Most of the time, we use the \attrib command, which assumes that its +% first argument, the object name, is an x-string and its second +% argument, the attribute name, is an i-string. Examples of the +% \attrib command: \attrib{A}{length}, \attrib{x}{next}, +% \attrib{\rho}{next-item}. \attrib is just a direct call to the +% \attribxi macro. + +% The four macros \attribxi, \attribxx, \attribix, and \attribii each +% take two arguments. The two letters at the end of the macro name +% determine, in order, how each argument is treated. x indicates that +% the argument should be an x-string, and i indicates that the +% argument should be an i-string. + +% Because we use a single letter to indicate most objects and a string +% of one or more letters to indicate most attribute names, \attribxi +% is the most common macro we use. That's why \attrib is just a +% direct call to \attribxi. + +% Use \attribxx when the object name is an x-string and the object +% name is also an x-string, for example, when the attribute name has a +% subscript: \attribxx{x}{c_i} or \attrib{x}{\id{key}_i}. Another +% time you would use \attribxx is when the attribute name is a Greek +% letter: \attrib{v}{\pi}. + +% When the object name has more than one letter, it is usually an +% i-string. In this case, use \attribii or \attribix, depending on +% the attribute name: \attribii{item}{key}, \attribii{prev-item}{np}, +% \attribix{item}{\pi}. + +% The \attribb, \attribbb, \attribbbb, and \attribbxxi macros are for +% cascading attributes. They just call the appropriate \attribxi and +% \attribxx commands. For one level of cascading, use \attribb: +% \attribb{x}{left}{size}. For two levels, use \attribbb: +% \attribbb{y}{p}{left}{size}. For three levels, use \attribbbb (but +% no examples in the book use this macro). The \attribbxxi macro is +% for one level of cascading where the first attribute given is an +% x-string: \attribbxxi{x}{c_i}{n}. + +% When the object is an edge of a graph, specified by two vertices, +% use \attribe or \attribex: \attribe{u}{v}{f}, \attribex{u}{v}{c'}. + +\newcommand{\attribxi}[2]{\ensuremath{#1.\hspace*{1pt}\id{#2}}} +\newcommand{\attribxx}[2]{\ensuremath{#1.\hspace*{1pt}#2}} +\newcommand{\attribix}[2]{\ensuremath{\id{#1}\hspace*{1pt}.#2}} +\newcommand{\attribii}[2]{\ensuremath{\id{#1}\hspace*{1pt}.\hspace*{1pt}\id{#2}}} +\newcommand{\attrib}[2]{\attribxi{#1}{#2}} +\newcommand{\attribe}[3]{\attribxi{(#1,#2)}{#3}} +\newcommand{\attribex}[3]{\attribxx{(#1,#2)}{#3}} +\newcommand{\attribb}[3]{\attribxi{\attribxi{#1}{#2}}{#3}} +\newcommand{\attribbb}[4]{\attribxi{\attribb{#1}{#2}{#3}}{#4}} +\newcommand{\attribbbb}[5]{\attribxi{\attribbb{#1}{#2}{#3}{#4}}{#5}} +\newcommand{\attribbxxi}[3]{\attribxi{\attribxx{#1}{#2}}{#3}} + +% 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\codeindent{\textbf{else} }% +\begin{tabbing}% +99\=\codeindent\=\codeindent\=\codeindent\=\codeindent\=\codeindent\=\codeindent\=\codeindent\=codeindent\=codeindent\=\+\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}} + +% Override the 'gets' symbol. +\def\gets{\mathrel{\hspace{1pt}=\hspace{1pt}}} +\newcommand{\isequal}{\mathrel{\scalebox{0.8}[1]{=}\hspace*{1pt}\scalebox{0.8}[1]{=}}} + +% All of our favorite keywords. +\newcommand{\For}{\textbf{for} } +\newcommand{\To}{\ifmmode\ \textrm{\textbf{to}}\ \else\textbf{to}\ \fi} +\newcommand{\By}{\ifmmode\ \textrm{\textbf{by}}\ \else\textbf{by}\ \fi} +\newcommand{\Downto}{\ifmmode\ \textrm{\textbf{downto}}\ \else\textbf{downto}\ \fi} +\newcommand{\While}{\textbf{while} } +\newcommand{\Repeat}{\textbf{repeat}\>\addtocounter{indent}{1}} +\newcommand{\Until}{\kill\addtocounter{indent}{-1}\liprint\textbf{until} } +\newcommand{\If}{\textbf{if} } +\newcommand{\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}{\>\addtocounter{indent}{1}} +\newcommand{\Return}{\textbf{return} } +\newcommand{\CommentSymbol}{\texttt{\textbf{/\hspace*{-0.3em}/}}} +\newcommand{\Comment}{\CommentSymbol\ } +\newcommand{\RComment}{\`\CommentSymbol\ } +\newcommand{\Goto}{\textbf{goto} } +\newcommand{\Error}{\textbf{error} } % optionally followed by string argument +\newcommand{\EndTest}{\textbf{:}} +\newcommand{\Spawn}{\ifmmode\textbf{spawn}\ \else\textbf{spawn} \fi} +\newcommand{\Sync}{\textbf{sync}} +\newcommand{\Parfor}{\textbf{parallel for} } + +% Indent the next line one level more +\newcommand{\Indentmore}{\addtocounter{indent}{1}} + +\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} + +% Temporarily make all lines indented so that they start at the end of +% a given text. +\newcommand{\Startalign}[1]{\\ \pushtabs\FakeIndent#1\=\kill} +\newcommand{\Stopalign}{\poptabs} +\newcommand{\FakeIndent}{\setcounter{thisindent}{\value{indent}}\putfakeindents} +\newcommand{\putfakeindents}{\ifnum\value{thisindent}>0\textbf{else }\addtocounter{thisindent}{-1}\putfakeindents\fi} + +\endinput diff --git a/macros/latex/contrib/clrscode3e/clrscode3e.tex b/macros/latex/contrib/clrscode3e/clrscode3e.tex new file mode 100644 index 0000000000..6ca1fdfdb8 --- /dev/null +++ b/macros/latex/contrib/clrscode3e/clrscode3e.tex @@ -0,0 +1,999 @@ +\documentclass[11pt]{article} +\usepackage{times} +\usepackage[mtpcal,mtphrb,zswash,subscriptcorrection]{mtpro2} +\usepackage{clrscode3e} +\usepackage{url} +\urlstyle{rm} +\input{page} + +\newcommand{\subheading}[1]{\subsubsection*{#1}} +\newcommand{\clrscodethree}{\texttt{clrscode3e}} +\newcommand{\Codebox}{\texttt{codebox}} +\newcommand{\defn}[1]{\textit{\textbf{#1}}} + +\begin{document} + +\title{Using the \clrscodethree{} Package in \LaTeXe} +\author{Thomas H. Cormen \\ thc@cs.dartmouth.edu} +\date{February 20, 2018} + +\maketitle + +\section{Introduction} +\label{sec:intro} + +This document describes how to use the \clrscodethree{} package in +\LaTeXe{} to typeset pseudocode in the style of \textit{Introduction +to Algorithms}, Third edition, by Cormen, Leiserson, Rivest, and Stein +(CLRS 3/e) \cite{CLRS09}. You use the commands\footnote{We use the +term ``command'' rather than ``macro'' throughout this document, +though ``macro'' would work just as well.} in the same way we did in +writing CLRS 3/e, and your output will look just like the pseudocode +in the text. + +\section{Setup} +\label{sec:setup} + +To get the \clrscodethree{} package, download +\url{http://www.cs.dartmouth.edu/~thc/clrscode/clrscode3e.sty}, and +put it where it will be found when you run \LaTeXe{}. To use the +package, include the following line in your source file: + +{\small +\begin{verbatim} +\usepackage{clrscode3e} +\end{verbatim} +} + +\noindent The \clrscodethree{} package itself includes the line + +{\small +\begin{verbatim} +\RequirePackage{graphics} % needed for \scalebox command +\end{verbatim} +} + +\noindent This line is necessary in order to get the right spacing for +the $\isequal$ symbol that we use for equality tests. Therefore, you +will need to have the \texttt{graphics} package installed and +available on your system. + +\section{Typesetting names} +\label{sec:names} + +Pseudocode in CLRS 3/e 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:] Use identifiers for variable names of more than +one character. When a variable name is just a single character, e.g., +the identifier~$j$ in line~1 of \proc{Insertion-Sort} on page~18, we +just typeset it in math mode rather than using the \verb`\id` command: +\verb`$j$`. + +\sloppy + +Do not typeset identifiers consisting of two or more characters, e.g., +the variable \id{key} in line~2 of \proc{Insertion-Sort}, in this way. +(See page~51 of Lamport \cite{Lamport93}.) Although \LaTeXe{} +provides the \verb`\mathit` command for typesetting multiletter +identifiers, use our \verb`\id` command instead: \verb`\id{key}`, +rather than \verb`\mathit{key}` or---horrors!---\verb`$key$`. Since +the \verb`\id` command may be used both in and out of math mode, the +source text + +\fussy + +{\small +\begin{verbatim} +Line~5 uses the variable \id{key} in the test $A[i] > \id{key}$. +\end{verbatim} +} + +\noindent will produce +\begin{quote} +Line~5 uses the variable \id{key} in the test $A[i] > \id{key}$. +\end{quote} + +To see how a dash turns into a hyphen, consider line~1 of +\proc{Find-Max-Crossing-Subarray} on page~71. It contains the +variable \id{left-sum}. Typesetting this variable name by +\verb`\id{left-sum}` produces a hyphen in the identifier, but +typesetting it by \verb`\mathit{left-sum}` would produce +$\mathit{left-sum}$, with a minus sign---rather than a hyphen---in the +identifier. + +\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 such as \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}`. The \verb`\const` command typesets a dash within +a constant name as a hyphen, so that, as on page~409, +\verb`\const{no-such-path}` will produce $\const{no-such-path}$. + +\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~44, $\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 Lamport \cite{Lamport93} +lists these ``log-like'' functions. + +\end{description} + +\section{Typesetting object attributes} +\label{sec:attributes} + +In the first two editions of the book, we used square brackets for +object attributes. For example, we represented the length of an +array~$A$ by $\id{length}[A]$. Based on requests from readers, we +switched to the object-like dot-notation in the third edition, so that +we now denote the length of array~$A$ by \attrib{A}{length}. + +You might think that you could typeset \attrib{A}{length} by +\verb`$A.\id{length}$`, but that would produce $A.\id{length}$, which +has not quite enough space after the dot. Therefore, we created a set +of commands to typeset object attributes. Each one may be used either +in or out of math mode. + +Most of the time, we use the \verb`\attrib` command, which takes two +arguments: the name of the object and the name of the attribute. +Let's make a couple of definitions: +\begin{itemize} + +\item An \defn{i-string} is a string that you would use in an +\verb`\id` command, typically one or more non-Greek letters, numerals, +or dashes. + +\item An \defn{x-string} is a string that you would not use in an +\verb`\id` command, typically because it has a subscript or one or +more Greek letters. + +\item As a special, and very common, case, a single non-Greek letter +can count as either an i-string or an x-string. + +\end{itemize} + +\noindent The \verb`\attrib` command works well when the object name +is an x-string and the attribute name is an \mbox{i-string}. For +example, to produce \attrib{A}{length}, use \verb`\attrib{A}{length}`. +Here, we treat the object name,~$A$, as an x-string. The attribute +name, \id{length}, is of course an i-string. + +If all your objects are x-strings and all your attributes are +i-strings, then the \verb`\attrib` command will be all you need. We +provide several other commands for other situations that arose when we +produced CLRS~3/e. + +The four basic attribute commands are \verb`\attribxi`, +\verb`\attribxx`, \verb`\attribii`, and \verb`\attribix`. Each takes +two arguments: the object name and the attribute name. The last two +letters of the command name tell you what type of strings the +arguments should be. The next-to-last letter tells you about the +object name, and the last letter tells you about the attribute name. +\verb`i` indicates that the argument will be treated as an \verb`\id`, +in which case the command calls the \verb`\id` command and also puts +the right amount of space between the argument and the dot. + +\begin{itemize} + +\item You may use \verb`\attribxi` precisely when you would use +\verb`\attrib`. In fact, \verb`\attrib` is just a call to +\verb`\attribxi`. + +\item Use \verb`\attribxx` when both the object name and attribute +names are x-strings. For example, you would use \verb`\attribxx` if +the attribute name has a subscript, so that to produce +\attribxx{y}{c_i}, you would use \verb`\attribxx{y}{c_i}`. Another +situation in which you would use \verb`\attribxx` is when the +attribute name is a Greek letter: to produce \attribxx{v}{\pi}, use +\verb`\attribxx{v}{\pi}`. + +\item If both the object name and attribute name are i-strings, then +you should use \verb`\attribii`. For example, +\verb`\attribii{item}{key}` produces \attribii{item}{key}, and +\verb`\attribii{prev-item}{np}` produces \attribii{prev-item}{np}. + +\item If the object name is an i-string and the attribute name is an +x-string, then use \verb`\attribix`. (We never had this situation +arise in CLRS 3/e.) But if we had wanted to produce +\attribix{item}{\pi}, we would have used \verb`\attribix{item}{\pi}`. + +\end{itemize} + +For convenience, the \clrscodethree{} package also contains commands +for cascading attributes, such as \attribb{x}{left}{size}. These +commands string together calls to the appropriate \verb`\attribxi` and +\verb`\attribxx` commands. The number of arguments they take depends +on how many attributes you are stringing together. + +\begin{itemize} + +\item When you have two attributes, use \verb`\attribb`, which takes +an object name and two attribute names: \verb`\attribb{x}{left}{size}` +produces \attribb{x}{left}{size}. This command assumes that the +object name is an x-string and both attribute names are i-strings. + +\item For three attributes, use \verb`\attribbb`, which takes an +object name (an x-string) and three object names (i-strings): to +produce \attribbb{y}{p}{left}{size}, use +\verb`\attribbb{y}{p}{left}{size}`. + +\item For four attributes, use \verb`\attribbbb`, which is like +\verb`\attribbb` but with one additional attribute tacked on. We +never needed to use this command in CLRS 3/e. + +\item The \verb`\attribbxxi` command is for one level of cascading +where the first attribute given is an \mbox{x-string}. For example, +\verb`\attribbxxi{x}{c_i}{n}` produces \attribbxxi{x}{c_i}{n}. + +\end{itemize} + +If your cascading attributes do not fit any of these descriptions, +you'll have to roll your own command from the \verb`\attribxx` and +\verb`\attribxi` (or \verb`\attrib`) commands. For example, suppose +you want to produce \attribxx{\attribxi{x}{left}}{\id{key_i}}. +Because it has a subscript, $\id{key}_i$ is an x-string, and so you +should not use \verb`\attribb`. Instead, use +\verb`\attribxx{\attribxi{x}{left}}{\id{key_i}}`. (You could replace +the call of \verb`\attribxi` by a call of \verb`\attrib`.) Note that +this call treats $\id{key_i}$ as an attribute of \attrib{x}{left}, +which is correct, rather than treating \attribii{left}{\id{key}_i} as +an attribute of~$x$, which is not correct. + +Edges of a graph can have attributes, too, and the \clrscodethree{} +package provides two commands for attributes of edges. These commands +assume that the edges are of the form $(u,v)$, where the vertices $u$ +and~$v$ are x-strings. They take three parameters: the two vertices +that define the edge and the name of the attribute. +\begin{itemize} + +\item When the attribute name is an i-string, use \verb`\attribe`. +For example, to produce \attribe{u}{v}{c}, use +\verb`\attribe{u}{v}{c}`. + +\item When the attribute name is an x-string, use \verb`\attribex`. +For example, to produce \attribex{u}{v}{c'}, use +\verb`\attribex{u}{v}{c'}`. + +\end{itemize} + +\section{Miscellaneous commands} +\label{sec:misc} + +The \clrscodethree{} package contains three commands that don't really +fit anywhere else, so let's handle them here. All three must be used +in math mode. + +\begin{itemize} + +\item 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]$. + +\item We use the \verb`\gets` command for the assignment operator. +For example, line~4 of \proc{Insertion-Sort} on page~18 is +\verb`$i \gets j - 1$`, producing $i \gets j - 1$. + +\item We use the \verb`\isequal` command to test for equality with the +$\isequal$ symbol. For example, line~1 of +\proc{Find-Maximum-Subarray} on page~72 contains the test $\id{high} +\isequal \id{low}$, which we get by typesetting +\verb`$\id{high} \isequal \id{low}$`. + +\end{itemize} + +You might wonder why we bother with the \verb`\gets` command when we +could just typeset an equals sign directly. The answer is that in the +first two editions of \textit{Introduction to Algorithms}, we used a +different symbol (a left arrow) for the assignment operator, and it +made sense to use a command for that. Many readers told us that they +preferred to use an equals sign for assignment---as many programming +languages use---and so we made this change for the third edition. But +it's a good idea to continue using the \verb`\gets` command so that we +can easily change our assignment operator should we desire to do so in +the future. + +Once we decided to use the equals sign for assignment, we could no +longer use it for equality tests. We created the \verb`\isequal` +command for equality tests, and we decided to base it on the double +equals sign used for equality tests in C, C++, and Java. Typesetting +it as \verb`==` in math mode produces $==$, which is too wide for our +tastes. Our \verb`\isequal` command calls the \verb`\scalebox` +command from the \texttt{graphics} package to narrow the symbol, and +it puts a nice amount of space between the equals signs: $\isequal$. + +\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 does not break across pages. + +\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, then you +should consider using other means in \LaTeXe, such as the +\texttt{minipage} environment. 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 on page~343 of CLRS 3/e.) After the line +containing the procedure name come one or more lines of code, usually +numbered. Some of the lines may be unnumbered, being continuations of +previous lines. Lines are usually numbered starting from~1, but again +there are exceptions, such as the pseudocode on page~343. + +\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~18: + +\pagebreak + +{\small +\begin{verbatim} +\begin{codebox} +\Procname{$\proc{Insertion-Sort}(A)$} +\li \For $j \gets 2$ \To $\attrib{A}{length}$ +\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 in the text editor to +every 4 characters when typing in and displaying pseudocode source +with the \clrscodethree{} 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)`. + +A \Codebox{} environment has a \verb`tabbing` environment within it. +Each tab stop gives one level of indentation. We designed the +indentation so that the body of an \kw{else} clause starts at just the +right 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. + +If you used the \texttt{clrscode} package from the second edition of +the book, you might notice different tabbing behavior when you port +your pseudocode to the \clrscodethree{} package. Where the +\texttt{clrscode} package used two tab stops for each level of loop +indentation, the \clrscodethree{} package uses just one tab stop. We +made this change in the \clrscodethree{} package because the third +edition eliminates the keyword \kw{then} and left-aligns \kw{else} +with its corresponding \kw{if}. + +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}, the commands +\verb`\For` and \verb`\While` produce the keywords \kw{for} and +\kw{while} in boldface within a \Codebox{}. + +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 the previous paragraph, I typed in +the following: + +{\small +\begin{verbatim} +As you can see from the source for \proc{Insertion-Sort}, the commands +\verb`\For` and \verb`\While` produce the keywords \kw{for} and +\kw{while} in boldface within a \texttt{codebox}. +\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` +(which does not appear in CLRS 3/e, but you might wish to use), +\verb`\Error`, \verb`\Spawn`, \verb`\Sync`, and \verb`\Parfor` (which +produces the compound keyword \mbox{\kw{parallel~for}}). 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 in pseudocode. The +\verb`\Comment` command simply produces the comment symbol +\CommentSymbol, followed by a space. To get the comment symbol +without a following space, use \verb`\CommentSymbol`. None of the +above commands affects indentation. + +\subheading{Loops} + +The \proc{Insertion-Sort} example above shows typical ways to typeset +\kw{for} and \kw{while} loops. In these loops, the important commands +are \verb`\Do` and \verb`\End`. \verb`\Do` increments the indentation +level to start the body. Put \verb`\Do` on a line starting with +\verb`\li`, but don't put either \verb`\li` or \verb`\zi` between the +\verb`\Do` command and the first statement of the loop body. Use +\verb`\li` or \verb`\zi` in front of all loop-body statements after +the first one. \verb`\End` simply decrements the indentation level, +and you use it to end any \kw{for} or \kw{while} loop, or otherwise +decrement the indentation level. + +In the first two editions of the book, the body of a \kw{for} or +\kw{while} loop began with the keyword \kw{do}. Responding to +requests from readers to make pseudocode more like C, C++, and Java, +we eliminated this keyword in the third edition. + +As you can see from the above example, I like to place each \verb`\Do` +and \verb`\End` on its own line. You can format your source text any +way you like, but I find that the way I format pseudocode makes it +easy to match up \verb`\Do`-\verb`\End` pairs. + +If you want your \kw{for} loop to decrease the loop variable in each +iteration, use \verb`\Downto` rather than \verb`\To`. If you want the +stride to be a value other than~$1$, use the \verb`\By` command. For +example, line~6 of \proc{Iterative-FFT} on page~917 is typeset as +\begin{verbatim} +\For $k \gets 0$ \To $n-1$ \By $m$ +\end{verbatim} + +Loops that use the \kw{repeat}-\kw{until} structure are a bit +different. We use the \verb`\Repeat` and \verb`\Until` +commands, as in the \proc{Hash-Insert} procedure on page~270: + +\pagebreak + +{\small +\begin{verbatim} +\begin{codebox} +\Procname{$\proc{Hash-Insert}(T,k)$} +\li $i \gets 0$ +\li \Repeat +\li $j \gets h(k,i)$ +\li \If $T[j] \isequal \const{nil}$ +\li \Then + $T[j] \gets k$ +\li \Return $j$ +\li \Else + $i \gets i+1$ + \End +\li \Until $i \isequal m$ +\li \Error ``hash table overflow'' +\end{codebox} +\end{verbatim} +} + +\noindent Note that the \verb`\Until` command has an implied +\verb`\End`. + +\subheading{Typesetting \kw{if} statements} + +As you can see from the above example of \proc{Hash-Insert}, we +typeset \kw{if} statements with the commands \verb`\If`, \verb`\Then`, +\verb`\Else`, and \verb`\End`. In the first two editions of the book, +the keyword \kw{then} appeared in pseudocode, but---again mindful of +requests from our readers to make our pseudocode more like C, C++, and +Java---we eliminated the keyword \kw{then} in the third edition. The +\verb`\Then` command remains, however, in order to indent the code +that runs when the test in the \kw{if} clause evaluates to +\const{true}. + +We use \verb`\End` to terminate an \kw{if} statement, whether or not +it has an \kw{else} clause. For an example of an \kw{if} statement +without an \kw{else} clause, here's the \proc{Merge-Sort} procedure on +page~34: + +{\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} +} + +Note: the command \verb`\floor` is our own. It is defined as + +{\small +\begin{verbatim} +\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} +\end{verbatim} +} + +The \proc{Hash-Insert} procedure above shows how to typeset an \kw{if} +statement that has an \kw{else} clause. For a more complicated +example, using nested \kw{if} statements, here's the +\proc{Cascading-Cut} procedure on page~519: + +\pagebreak + +{\small +\begin{verbatim} +\begin{codebox} +\Procname{$\proc{Cascading-Cut}(H,y)$} +\li $z \gets \attrib{y}{p}$ +\li \If $z \neq \const{nil}$ +\li \Then + \If $\attrib{y}{mark} \isequal \const{false}$ +\li \Then $\attrib{y}{mark} \gets \const{true}$ +\li \Else + $\proc{Cut}(H,y,z)$ +\li $\proc{Cascading-Cut}(H,z)$ + \End + \End +\end{codebox} +\end{verbatim} +} + +\noindent Note that \verb`\Then` and \verb`\Else` always follow an +\verb`\li` command to start a new numbered line. As with the +\verb`\Do` command, don't put either \verb`\li` or \verb`\zi` between +\verb`\Then` or \verb`\Else` and the statement that follows. + +As you can see, I 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 one short line, such as in line~4 of +\proc{Cascading-Cut}. + +Sometimes, you need more complicated ``\kw{if}-ladders'' than you can +get from the \verb`\Then` and \verb`\Else` commands. The +\proc{Transplant} procedure on page~296 provides an example, +and it uses the \verb`\ElseIf` and \verb`\ElseNoIf` commands: + +{\small +\begin{verbatim} +\begin{codebox} +\Procname{$\proc{Transplant}(T, u, v)$} +\li \If $\attrib{u}{p} \isequal \const{nil}$ +\li \Then $\attrib{T}{root} \gets v$ +\li \ElseIf $u \isequal \attribb{u}{p}{left}$ +\li \Then $\attribb{u}{p}{left} \gets v$ +\li \ElseNoIf + $\attribb{u}{p}{right} \gets v$ + \End +\li \If $v \neq \const{nil}$ +\li \Then $\attrib{v}{p} \gets \attrib{u}{p}$ + \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` followed by +\verb`\Then` for all intermediate cases. You use \verb`\ElseNoIf` +like you use \verb`\Else` in that it follows an \verb`\li` command, +you don't follow it with \verb`\Then`, and, because it terminates an +\kw{if}-ladder, it's followed by \verb`\End`. I usually line up the +terminating \verb`\End` with \verb`\If`, the \verb`\ElseIf` commands, +and \verb`\ElseNoIf`, but the way you line it up won't change the +typeset output. + +As another example, here is the \proc{Segments-Intersect} procedure on +page~1018: + +\pagebreak + +{\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 \isequal 0$ and $\proc{On-Segment}(p_3, p_4, p_1)$ +\li \Then \Return \const{true} +\li \ElseIf $d_2 \isequal 0$ and $\proc{On-Segment}(p_3, p_4, p_2)$ +\li \Then \Return \const{true} +\li \ElseIf $d_3 \isequal 0$ and $\proc{On-Segment}(p_1, p_2, p_3)$ +\li \Then \Return \const{true} +\li \ElseIf $d_4 \isequal 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 levels} + +In the \proc{Segments-Intersect} procedure, we 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} +} + +\noindent Whenever the indentation level is nonzero upon hitting an +\verb`\end{codebox}` command, you'll get a warning telling you what +the indentation level was. + +\subheading{Tabs and comments} + +Line~3 of \proc{Insertion-Sort} shows how to make a line that is only +a comment. It's a little more tricky to put a comment at the end of a +line of code. Using the tab command \verb`\>`, explicitly tab to +where you want the comment to begin and then use the \verb`\Comment` +command to produce the comment symbol. When several lines contain +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~1005: + +{\footnotesize +\begin{verbatim} +\begin{codebox} +\Procname{$\proc{KMP-Matcher}(T,P)$} +\li $n \gets \attrib{T}{length}$ +\li $m \gets \attrib{P}{length}$ +\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}\ne \Tx{i}$ +\li \Do $q \gets \pi[q]$\>\>\>\>\>\>\Comment next character does not match + \End +\li \If $\Px{q+1} \isequal \Tx{i}$ +\li \Then $q \gets q+1$\>\>\>\>\>\>\Comment next character matches + \End +\li \If $q \isequal 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. + +Note: the commands \verb`\Px` and \verb`\Tx` are our own, with the +definitions + +{\small +\begin{verbatim} +\newcommand{\Px}[1]{P[#1]} +\newcommand{\Tx}[1]{T[#1]} +\end{verbatim} +} + +We used the command \verb`\RComment` to justify a comment against the +right margin. We used this command only in the \proc{RB-Insert-Fixup} +procedure on page~316 and the \proc{RB-Delete-Fixup} procedure on +page~326. For example, here's how we typeset line~5 of +\proc{RB-Insert-Fixup}: + +{\small +\begin{verbatim} +\li \Then + $\attribb{z}{p}{color}\gets \const{black}$ + \RComment case 1 +\end{verbatim} +} + +\subheading{Referencing line numbers} + +The source files for CLRS 3/e contain 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~18: + +\pagebreak + +{\small +\begin{verbatim} +\begin{codebox} +\Procname{$\proc{Insertion-Sort}(A)$} +\li \For $j \gets 2$ \To $\attrib{A}{length}$ + \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 Indentation indicates block structure. 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~657, we want the line +number to be the same as a line number within the +\proc{Dag-Shortest-Paths} procedure on page~655. 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 \attrib{G}{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 on page~343, where the first line number had to be +one greater than the number of the last line of \proc{Left-Rotate} on +page~313. Use the \verb`setlinenumberplus` command: + +{\small +\begin{verbatim} +\begin{codebox} +\setlinenumberplus{li:left-rot-parent}{1} +\li $\attrib{y}{size} \gets \attrib{x}{size}$ +\li $\attrib{x}{size} \gets \attribb{x}{left}{size} + + \attribb{x}{right}{size} + 1 +\end{codebox} +\end{verbatim} +} + +\noindent Here, the last line of \proc{Left-Rotate} has +\verb`\label{li:left-rot-parent}`. + +\subheading{Indenting long argument lists in procedure calls} + +You might find that you have to call a procedure with an argument list +so long that the call requires more than one line. When this +situation arises, it often looks best to align the second and +subsequent lines of arguments with the first argument. The only place +we did so was in the $\proc{Sum-Arrays}'$ procedure in Problem~27-1 on +page~805. + +To get this style of alignment, use the \verb`\Startalign` and +\verb`\Stopalign` commands, in concert with the \verb`\>` command of +\LaTeXe{}. The \verb`\Startalign` command takes an argument that is +the text string that you wish to align just to the right of. Start +each line that you want to indent with \verb`\>`. Use the +\verb`\Stopalign` command to restore indentation to its state from +before the \verb`\Startalign` command. + +The source code for $\proc{Sum-Arrays}'$ shows how to use these +commands: + +\pagebreak + +{\small +\begin{verbatim} +\begin{codebox} +\Procname{$\proc{Sum-Arrays}{$'$}(A, B, C)$} +\li $n \gets \attrib{A}{length}$ +\li $\id{grain-size} \gets\ \ ?$ \>\>\>\>\>\>\Comment to be determined +\li $r \gets \ceil{n/\id{grain-size}}$ +\li \For $k \gets 0$ \To $r-1$ +\li \Do + \Spawn $\proc{Add-Subarray}(A, B, C, k\cdot\id{grain-size}+1,$ +\Startalign{\Spawn $\proc{Add-Subarray}($} +\> $\min((k+1)\cdot\id{grain-size}, n))$ +\Stopalign + \End +\li \Sync +\end{codebox} +\end{verbatim} +} + +\noindent The second line of arguments in the call to +\proc{Add-Subarray} starts right under the first parameter, $A$, in +the call. + +\section{Reporting bugs} +\label{sec:bugs} + +If you find errors in the \clrscodethree{} 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{clrscode3e.sty} file contains the following disclaimer: + +{\small +\begin{verbatim} +% Written for general distribution by Thomas H. Cormen, March 2009. + +% 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 20 February 2018. Included definitions for the commands +\verb`\floor`, \verb`\Px`, and \verb`\Tx`. Changed \verb`\procdecl` +and \verb`\procdecltag` commands to \verb`\proc`. + +\item 27 January 2010. Corrected an error in the documentation. The +first line after a \verb`\Repeat` command should begin with +\verb`\li`. + +\item 23 March 2009. Initial revision of document and code. + +\end{itemize} + +\begin{thebibliography}{9} + +\bibitem{CLRS09} Thomas H. Cormen, Charles E. Leiserson, Ronald L. +Rivest, and Clifford Stein. \textit{Introduction to Algorithms}, +third edition. The MIT Press, 2009. + +\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/clrscode3e/page.tex b/macros/latex/contrib/clrscode3e/page.tex new file mode 100644 index 0000000000..de6c87bfc8 --- /dev/null +++ b/macros/latex/contrib/clrscode3e/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} |