From e0c6872cf40896c7be36b11dcc744620f10adf1d Mon Sep 17 00:00:00 2001 From: Norbert Preining Date: Mon, 2 Sep 2019 13:46:59 +0900 Subject: Initial commit --- macros/latex/contrib/clrscode/README | 2 + macros/latex/contrib/clrscode/clrscode.pdf | Bin 0 -> 38588 bytes macros/latex/contrib/clrscode/clrscode.sty | 288 +++++++++++ macros/latex/contrib/clrscode/clrscode.tex | 744 +++++++++++++++++++++++++++++ macros/latex/contrib/clrscode/page.tex | 18 + 5 files changed, 1052 insertions(+) create mode 100644 macros/latex/contrib/clrscode/README create mode 100644 macros/latex/contrib/clrscode/clrscode.pdf create mode 100644 macros/latex/contrib/clrscode/clrscode.sty create mode 100644 macros/latex/contrib/clrscode/clrscode.tex create mode 100644 macros/latex/contrib/clrscode/page.tex (limited to 'macros/latex/contrib/clrscode') 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 Binary files /dev/null and b/macros/latex/contrib/clrscode/clrscode.pdf 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} -- cgit v1.2.3