From a761f9aaf524bb1b1eb40d89f279c133cabee9d5 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Wed, 21 Jun 2006 16:10:17 +0200 Subject: [PATCH] doc: user guide Mostly copied from my thesis text. --- doc/Internal.tex | 787 +++++++++++++++++++++++++ doc/Usage.tex | 237 ++++++++ doc/barvinok.bib | 83 +++ doc/barvinok.gdf | 65 ++ doc/barvinok.tex | 26 + doc/chicago.bst | 1726 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ doc/chicago.sty | 318 ++++++++++ doc/mydefs.sty | 198 +++++++ 8 files changed, 3440 insertions(+) create mode 100644 doc/Internal.tex create mode 100644 doc/Usage.tex create mode 100644 doc/barvinok.bib create mode 100644 doc/barvinok.gdf create mode 100644 doc/barvinok.tex create mode 100644 doc/chicago.bst create mode 100644 doc/chicago.sty create mode 100644 doc/mydefs.sty diff --git a/doc/Internal.tex b/doc/Internal.tex new file mode 100644 index 0000000..111a766 --- /dev/null +++ b/doc/Internal.tex @@ -0,0 +1,787 @@ +\section{Internal Representation of the \protect\ai[\tt]{barvinok} library} + +Our \barvinok/ library is built on top of \PolyLib/ +\shortcite{Wilde1993,Loechner1999}. +In particular, it reuses the implementations +of the algorithm of +\shortciteN{Loechner97parameterized} +for computing parametric vertices +and the algorithm of +\shortciteN{Clauss1998parametric} +for computing chamber decompositions. +Initially, our library was meant to be a replacement +for the algorithm of \shortciteN{Clauss1998parametric}, +also implemented in \PolyLib/, for computing quasi-polynomials. +To ease the transition of application programs we +tried to reuse the existing data structures as much as possible. + +\subsection{Existing Data Structures} +\label{a:existing} + +Inside \PolyLib/ integer values are represented by the +\ai[\tt]{Value} data type. +Depending on a configure option, the data type may +either by a 32-bit integer, a 64-bit integer +or an arbitrary precision integer using \ai[\tt]{GMP}. +The \barvinok/ library requires that \PolyLib/ is compiled +with support for arbitrary precision integers. + +The basic structure for representing (unions of) polyhedra is a +\ai[\tt]{Polyhedron}. +\begin{verbatim} +typedef struct polyhedron { + unsigned Dimension, NbConstraints, NbRays, NbEq, NbBid; + Value **Constraint; + Value **Ray; + Value *p_Init; + int p_Init_size; + struct polyhedron *next; +} Polyhedron; +\end{verbatim} +The attribute \ai[\tt]{Dimension} is the dimension +of the ambient space, i.e., the number of variables. +The attributes \ai[\tt]{Constraint} +and \ai[\tt]{Ray} point to two-dimensional arrays +of constraints and generators, respectively. +The number of rows is stored in +\ai[\tt]{NbConstraints} and +\ai[\tt]{NbRays}, respectively. +The number of columns in both arrays is equal +to \verb!1+Dimension+1!. +The first column of \ai[\tt]{Constraint} is either +$0$ or $1$ depending on whether the constraint +is an equality ($0$) or an inequality ($1$). +The number of equalities is stored in \ai[\tt]{NbEq}. +If the constraint is $\sp a x + c \ge 0$, then +the next columns contain the coefficients $a_i$ +and the final column contains the constant $c$. +The first column of \ai[\tt]{Ray} is either +$0$ or $1$ depending on whether the generator +is a line ($0$) or a vertex or ray ($1$). +The number of lines is stored in \ai[\tt]{NbBid}. +Let $d$ be the \ac{lcm} of the denominators of the coordinates +of a vertex $\vec v$, then the next columns contain +$d v_i$ and the final column contains $d$. +For a ray, the final column contains $0$. +The field \ai[\tt]{next} points to the next polyhedron in +the union of polyhedra. +It is \verb+0+ if this is the last (or only) polyhedron in the union. +For more information on this structure, we refer to \shortciteN{Wilde1993}. + +Quasi-polynomials are represented using the +\ai[\tt]{evalue} and \ai[\tt]{enode} structures. +\begin{verbatim} +typedef enum { polynomial, periodic, evector } enode_type; + +typedef struct _evalue { + Value d; /* denominator */ + union { + Value n; /* numerator (if denominator != 0) */ + struct _enode *p; /* pointer (if denominator == 0) */ + } x; +} evalue; + +typedef struct _enode { + enode_type type; /* polynomial or periodic or evector */ + int size; /* number of attached pointers */ + int pos; /* parameter position */ + evalue arr[1]; /* array of rational/pointer */ +} enode; +\end{verbatim} +If the field \ai[\tt]{d} of an \ai[\tt]{evalue} is zero, then +the \ai[\tt]{evalue} is a placeholder for a pointer to +an \ai[\tt]{enode}, stored in \ai[\tt]{x.p}. +Otherwise, the \ai[\tt]{evalue} is a rational number with +numerator \ai[\tt]{x.n} and denominator \ai[\tt]{d}. +An \ai[\tt]{enode} is either a \ai[\tt]{polynomial} +or a \ai[\tt]{periodic}, depending on the value +of \ai[\tt]{type}. +The length of the array \ai[\tt]{arr} is stored in \ai[\tt]{size}. +For a \ai[\tt]{polynomial}, \ai[\tt]{arr} contains the coefficients. +For a \ai[\tt]{periodic}, it contains the values for the different +residue classes modulo the parameter indicated by \ai[\tt]{pos}. +For a polynomial, \ai[\tt]{pos} refers to the variable +of the polynomial. +The value of \ai[\tt]{pos} is \verb+1+ for the first parameter. +That is, if the value of \ai[\tt]{pos} is \verb+1+ and the first +parameter is $p$, and if the length of the array is $l$, +then in case it is a polynomial, the + \ai[\tt]{enode} represents +$$ +\verb+arr[0]+ + \verb+arr[1]+ p + \verb+arr[2]+ p^2 + \cdots + +\verb+arr[l-1]+ p^{l-1} +. +$$ +If it is a periodic, then it represents +$$ +\left[ +\verb+arr[0]+, \verb+arr[1]+, \verb+arr[2]+, \ldots, +\verb+arr[l-1]+ +\right]_p +. +$$ +Note that the elements of a \ai[\tt]{periodic} may themselves +be other \ai[\tt]{periodic}s or even \ai[\tt]{polynomial}s. +In our library, we only allow the elements of a \ai[\tt]{periodic} +to be other \ai[\tt]{periodic}s or rational numbers. +The chambers and their corresponding quasi-polynomial are +stored in \ai[\tt]{Enumeration} structures. +\begin{verbatim} +typedef struct _enumeration { + Polyhedron *ValidityDomain; /* constraints on the parameters */ + evalue EP; /* dimension = combined space */ + struct _enumeration *next; /* Ehrhart Polynomial, + corresponding to parameter + values inside the domain + ValidityDomain above */ +} Enumeration; +\end{verbatim} +For more information on these structures, we refer to \shortciteN{Loechner1999}. + +\begin{example} +Figure~\ref{f:Loechner} is a skillful reconstruction +of Figure~2 from \shortciteN{Loechner1999}. +It shows the contents of the \ai[\tt]{enode} structures +representing the quasi-polynomial +$ +[1,2]_p p^2 + 3 p + \frac 5 2 +$. + +\begin{figure} +\begin{xy} +\POS(0,0)*!UL{\hbox{ +\tt +\begin{tabular}{|c|c|c|} +\hline +\multicolumn{2}{|c|}{type} & polynomial \\ +\hline +\multicolumn{2}{|c|}{size} & 3 \\ +\hline +\multicolumn{2}{|c|}{pos} & 1 \\ +\hline +\smash{\lower 6.25pt\hbox{arr[0]}} & d & 2 \\ +\cline{2-3} + & x.n & 5 \\ +\hline +\smash{\lower 6.25pt\hbox{arr[1]}} & d & 1 \\ +\cline{2-3} + & x.n & 3 \\ +\hline +\smash{\lower 6.25pt\hbox{arr[2]}} & d & 0 \\ +\cline{2-3} + & x.p & \\ +\hline +\end{tabular} +} +}="box1" ++DR*!DR\hbox{\strut\hskip 1.5\tabcolsep\phantom{\tt polynomial}\hskip 1.5\tabcolsep}+C="a" +\POS(60,-15)*!UL{\hbox{ +\tt +\begin{tabular}{|c|c|c|} +\hline +\multicolumn{2}{|c|}{type} & periodic \\ +\hline +\multicolumn{2}{|c|}{size} & 2 \\ +\hline +\multicolumn{2}{|c|}{pos} & 1 \\ +\hline +\smash{\lower 6.25pt\hbox{arr[0]}} & d & 1 \\ +\cline{2-3} + & x.n & 1 \\ +\hline +\smash{\lower 6.25pt\hbox{arr[1]}} & d & 1 \\ +\cline{2-3} + & x.n & 2 \\ +\hline +\end{tabular} +} +}="box2" ++UL+<0.5\tabcolsep,0pt>*!UL\hbox{\strut}+CL="b" +\POS"a"\ar@(r,l) "b" +\POS"box1"+UC*++!D\hbox{\tt enode} +\POS"box2"+UC*++!D\hbox{\tt enode} +\end{xy} +\caption{The quasi-polynomial $[1,2]_p p^2 + 3 p + \frac 5 2$.} +\label{f:Loechner} +\end{figure} +\end{example} + +\subsection{Data Structures for Quasi-polynomials} +\label{a:data} + +Internally, we do not represent our quasi-polynomials +as step-polynomials, but, similarly to \shortciteN{Loechner1999}, +as polynomials with periodic numbers for coefficients. +However, we also allow our periodic numbers to be represented by +fractional parts of degree-$1$ polynomials rather than +an explicit enumeration using the \ai[\tt]{periodic} type. +By default, the current version of \barvinok/ uses +\ai[\tt]{periodic}s, but this can be changed through +the \ai[\tt]{--enable-fractional} configure option. +In the latter case, the quasi-polynomial using fractional +parts can also be converted to an actual step-polynomial +using \ai[\tt]{evalue\_frac2floor}, but this is not fully +supported yet. + +For reasons of compatibility,% +\footnote{Also known as laziness.} +we shoehorned our representations for piecewise quasi-polynomials +into the existing data structures. +To this effect, we introduced four new types, +\ai[\tt]{fractional}, \ai[\tt]{relation}, +\ai[\tt]{partition} and \ai[\tt]{flooring}. +\begin{verbatim} +typedef enum { polynomial, periodic, evector, fractional, + relation, partition, flooring } enode_type; +\end{verbatim} +The field \ai[\tt]{pos} is not used in most of these +additional types and is therefore set to \verb+-1+. + +The types \ai[\tt]{fractional} and \ai[\tt]{flooring} +represent polynomial expressions in a fractional part or a floor respectively. +The generator is stored in \verb+arr[0]+, while the +coefficients are stored in the remaining array elements. +That is, an \ai[\tt]{enode} of type \ai[\tt]{fractional} +represents +$$ +\verb+arr[1]+ + \verb+arr[2]+ \{\verb+arr[0]+\} + +\verb+arr[3]+ \{\verb+arr[0]+\}^2 + \cdots + +\verb+arr[l-1]+ \{\verb+arr[0]+\}^{l-2} +. +$$ +An \ai[\tt]{enode} of type \ai[\tt]{flooring} +represents +$$ +\verb+arr[1]+ + \verb+arr[2]+ \lfloor\verb+arr[0]+\rfloor + +\verb+arr[3]+ \lfloor\verb+arr[0]+\rfloor^2 + \cdots + +\verb+arr[l-1]+ \lfloor\verb+arr[0]+\rfloor^{l-2} +. +$$ + +\begin{example} +The internal representation of the quasi-polynomial +$$\left(1+2 \left\{\frac p 2\right\}\right) p^2 + 3 p + \frac 5 2$$ +is shown in Figure~\ref{f:fractional}. + +\begin{figure} +\begin{xy} +\POS(0,0)*!UL{\hbox{ +\tt +\begin{tabular}{|c|c|c|} +\hline +\multicolumn{2}{|c|}{type} & polynomial \\ +\hline +\multicolumn{2}{|c|}{size} & 3 \\ +\hline +\multicolumn{2}{|c|}{pos} & 1 \\ +\hline +\smash{\lower 6.25pt\hbox{arr[0]}} & d & 2 \\ +\cline{2-3} + & x.n & 5 \\ +\hline +\smash{\lower 6.25pt\hbox{arr[1]}} & d & 1 \\ +\cline{2-3} + & x.n & 3 \\ +\hline +\smash{\lower 6.25pt\hbox{arr[2]}} & d & 0 \\ +\cline{2-3} + & x.p & \\ +\hline +\end{tabular} +} +}="box1" ++DR*!DR\hbox{\strut\hskip 1.5\tabcolsep\phantom{\tt polynomial}\hskip 1.5\tabcolsep}+C="a" +\POS(60,0)*!UL{\hbox{ +\tt +\begin{tabular}{|c|c|c|} +\hline +\multicolumn{2}{|c|}{type} & fractional \\ +\hline +\multicolumn{2}{|c|}{size} & 3 \\ +\hline +\multicolumn{2}{|c|}{pos} & -1 \\ +\hline +\smash{\lower 6.25pt\hbox{arr[0]}} & d & 0 \\ +\cline{2-3} + & x.p & \\ +\hline +\smash{\lower 6.25pt\hbox{arr[1]}} & d & 1 \\ +\cline{2-3} + & x.n & 1 \\ +\hline +\smash{\lower 6.25pt\hbox{arr[2]}} & d & 1 \\ +\cline{2-3} + & x.n & 2 \\ +\hline +\end{tabular} +} +}="box2" ++UL+<0.5\tabcolsep,0pt>*!UL\hbox{\strut}+CL="b" +\POS"a"\ar@(r,l) "b" +\POS"box2"+UR*!UR{\hbox{ +\tt +\begin{tabular}{|c|} +\hline + fractional \\ +\hline + 3 \\ +\hline + -1 \\ +\hline + 0 \\ +\hline +\end{tabular} +} +}+CD*!U{\strut}+C="c" +\POS(60,-50)*!UL{\hbox{ +\tt +\begin{tabular}{|c|c|c|} +\hline +\multicolumn{2}{|c|}{type} & polynomial \\ +\hline +\multicolumn{2}{|c|}{size} & 2 \\ +\hline +\multicolumn{2}{|c|}{pos} & 1 \\ +\hline +\smash{\lower 6.25pt\hbox{arr[0]}} & d & 1 \\ +\cline{2-3} + & x.n & 0 \\ +\hline +\smash{\lower 6.25pt\hbox{arr[1]}} & d & 2 \\ +\cline{2-3} + & x.n & 1 \\ +\hline +\end{tabular} +} +}="box3" ++UR-<0.8\tabcolsep,0pt>*!UR\hbox{\strut}+CR="d" +\POS"c"\ar@(r,r) "d" +\POS"box1"+UC*++!D\hbox{\tt enode} +\POS"box2"+UC*++!D\hbox{\tt enode} +\POS"box3"+UC*++!D\hbox{\tt enode} +\end{xy} +\caption{The quasi-polynomial +$\left(1+2 \left\{\frac p 2\right\}\right) p^2 + 3 p + \frac 5 2$.} +\label{f:fractional} +\end{figure} + +\end{example} + +The \ai[\tt]{relation} type is used to represent \ai{stride}s. +In particular, if the value of \ai[\tt]{size} is 2, then +the value of a \ai[\tt]{relation} is (in pseudo-code): +\begin{verbatim} +(value(arr[0]) == 0) ? value(arr[1]) : 0 +\end{verbatim} +If the size is 3, then the value is: +\begin{verbatim} +(value(arr[0]) == 0) ? value(arr[1]) : value(arr[2]) +\end{verbatim} +The type of \verb+arr[0]+ is typically \ai[\tt]{fractional}. + +Finally, the \ai[\tt]{partition} type is used to +represent piecewise quasi-polynomials. +We prefer to encode this information inside \ai[\tt]{evalue}s +themselves +rather than using \ai[\tt]{Enumeration}s since we want +to perform the same kinds of operations on both quasi-polynomials +and piecewise quasi-polynomials. +An \ai[\tt]{enode} of type \ai[\tt]{partition} may not be nested +inside another \ai[\tt]{enode}. +The size of the array is twice the number of ``chambers''. +Pointers to chambers are stored in the even slots, +whereas pointer to the associated quasi-polynomials +are stored in the odd slots. +To be able to store pointers to chambers, the +definition of \ai[\tt]{evalue} was changed as follows. +\begin{verbatim} +typedef struct _evalue { + Value d; /* denominator */ + union { + Value n; /* numerator (if denominator > 0) */ + struct _enode *p; /* pointer (if denominator == 0) */ + Polyhedron *D; /* domain (if denominator == -1) */ + } x; +} evalue; +\end{verbatim} +Note that we allow a ``chamber'' to be a union of polyhedra +as discussed in Section~\ref{s:addition}. +Chambers with extra variables, i.e., those of Section~\ref{s:line}, +are only partially supported. +The field \ai[\tt]{pos} is set to the actual dimension, +i.e., the number of parameters. + +\subsection{Operations on Quasi-polynomials} +\label{a:operations} + +In this section we discuss some of the more important +operations on \ai[\tt]{evalue}s provided by the +\barvinok/ library. +Some of these operations are extensions +of the functions from \PolyLib/ with the same name. + +\begin{verbatim} +void eadd(evalue *e1,evalue *res); +void emul (evalue *e1, evalue *res ); +\end{verbatim} +The functions \ai[\tt]{eadd} and \ai[\tt]{emul} takes +two (pointers to) \ai[\tt]{evalue}s \verb+e1+ and \verb+res+ +and computes their sum and product respectively. +The result is stored in \verb+res+, overwriting (and deallocating) +the original value of \verb+res+. +It is an error if exactly one of +the arguments of \ai[\tt]{eadd} is of type \ai[\tt]{partition} +(unless the other argument is \verb+0+). +The addition and multiplication operations are described +in Sections~\ref{s:addition} and~\ref{s:multiplication} +respectively. + +The function \ai[\tt]{eadd} is an extension of the function +\ai[\tt]{new\_eadd} from \shortciteN{Seghir2002}. +Apart from supporting the additional types from Appendix~\ref{a:data}, +the new version also additionally imposes an order on the nesting of +different \ai[\tt]{enode}s. +Without such an ordering, \ai[\tt]{evalue}s could be constructed +representing for example +$$ +(0 y^ 0 + ( 0 x^0 + 1 x^1 ) y^1 ) x^0 + (0 y^0 - 1 y^1) x^1 +, +$$ +which is just a funny way of saying $0$. + +\begin{verbatim} +void eor(evalue *e1, evalue *res); +\end{verbatim} +The function \ai[\tt]{eor} implements the \ai{union} +operation from Section~\ref{s:set}. Both arguments +are assumed to correspond to indicator functions. + +\begin{verbatim} +evalue *esum(evalue *E, int nvar); +\end{verbatim} +The function \ai[\tt]{esum} performs the summation +operation from Section~\ref{s:summation}. +The piecewise step-polynomial represented by \verb+E+ is summated +over its first \verb+nvar+ variables. +Note that \verb+E+ must be zero or of type \ai[\tt]{partition}. +The function returns the result in a newly allocated +\ai[\tt]{evalue}. +Note also that \verb+E+ needs to have been converted +from \ai[\tt]{fractional}s to \ai[\tt]{flooring}s using +the function \ai[\tt]{evalue\_frac2floor}. +\begin{verbatim} +void evalue_frac2floor(evalue *e); +\end{verbatim} +This function also ensures that the arguments of the +\ai[\tt]{flooring}s are positive in the relevant chambers. +It currently assumes that the argument of each +\ai[\tt]{fractional} in the original \ai[\tt]{evalue} +has a minimum in the corresponding chamber. + +\begin{verbatim} +double compute_evalue(evalue *e,Value *list_args); +Value *compute_poly(Enumeration *en,Value *list_args); +\end{verbatim} +The functions \ai[\tt]{compute\_evalue} and +\ai[\tt]{compute\_poly} evaluate a (piecewise) quasi-polynomial +at a certain point. The argument \verb+list_args+ +points to an array of \ai[\tt]{Value}s that is assumed +to be long enough. +The \verb+double+ return value of \ai[\tt]{compute\_evalue} +is inherited from \PolyLib/. + +\begin{verbatim} +void print_evalue(FILE *DST,evalue *e,char **pname); +\end{verbatim} +The function \ai[\tt]{print\_evalue} dumps a human-readable +representation to the stream pointed to by \verb+DST+. +The argument \verb+pname+ points +to an array of character strings representing the parameter names. +The array is assumed to be long enough. + +\begin{verbatim} +int eequal(evalue *e1,evalue *e2); +\end{verbatim} +The function \ai[\tt]{eequal} return true (\verb+1+) if its +two arguments are structurally identical. +I.e., it does {\em not\/} check whether the two +(piecewise) quasi-polynomial represent the same function. + +\begin{verbatim} +void reduce_evalue (evalue *e); +\end{verbatim} +The function \ai[\tt]{reduce\_evalue} performs some +simplifications on \ai[\tt]{evalue}s. +Here, we only describe the simplifications that are directly +related to the internal representation. +Some other simplifications are explained in Section~\ref{s:simplification}. +If the highest order coefficients of a \ai[\tt]{polynomial}, +\ai[\tt]{fractional} or \ai[\tt]{flooring} are zero (possibly +after some other simplifications), then the size of the array +is reduced. If only the constant term remains, i.e., +the size is reduced to $1$ for \ai[\tt]{polynomial} or to $2$ +for the other types, then the whole node is replaced by +the constant term. +Additionally, if the argument of a \ai[\tt]{fractional} +has been reduced to a constant, then the whole node +is replaced by its partial evaluation. +A \ai[\tt]{relation} is similarly reduced if its second +branch or both its branches are zero. +Chambers with zero associated quasi-polynomials are +discarded from a \ai[\tt]{partition}. + +\subsection{Generating Functions} + +The representation of \rgf/s uses +some basic types from the \ai[\tt]{NTL} library +for representing arbitrary precision integers +(\ai[\tt]{ZZ}) +as well as vectors (\ai[\tt]{vec\_ZZ}) and matrices (\ai[\tt]{mat\_ZZ}) +of such integers. +Each term in a \rgf/ is represented by a \ai[\tt]{short\_rat} +structure. +\begin{verbatim} +struct short_rat { + struct { + /* rows: terms in numerator */ + mat_ZZ coeff; + mat_ZZ power; + } n; + struct { + /* rows: factors in denominator */ + mat_ZZ power; + } d; +}; +\end{verbatim} +The fields \ai[\tt]{n} and \ai[\tt]{d} represent the +numerator and the denominator respectively. +Note that in our implementation we combine terms +with the same denominator. +In the numerator, each row of \ai[\tt]{coeff} and \ai[\tt]{power} +represents a single such term. +The matrix \ai[\tt]{coeff} has two columns, one for the +numerator and one for the denominator of the rational coefficient +$\alpha_i$ of each term. +The columns of \ai[\tt]{power} correspond to the powers +of the variables. +In the denominator, each row of \ai[\tt]{power} +corresponds to the power $\vec b_{ij}$ of a +factor in the denominator. + +\begin{example} +Figure~\ref{fig:rat} +shows the internal representation of +$$ +\frac{\frac 3 2 \, x_0^2 x_1^3 + 2 \, x_0^5 x_1^{-7}} +{ (1 - x_0 x_1^{-3}) (1 - x_1^2)} +. +$$ + +\begin{figure} +\begin{center} +\begin{minipage}{0cm} +\begin{xy} +*\hbox{ +\tt +\begin{tabular}{|c|c|c|} +\hline +n.coeff & 3 & 2 \\ +\cline{2-3} + & 2 & 1 \\ +\hline +n.power & 2 & 3 \\ +\cline{2-3} + & 5 & -7 \\ +\hline +d.power & 1 & -3 \\ +\cline{2-3} + & 0 & 2 \\ +\hline +\end{tabular} +}+UC*++!D\hbox{\tt short\_rat} +\end{xy} +\end{minipage} +\end{center} +\caption{Representation of +$ +\left(\frac 3 2 \, x_0^2 x_1^3 + 2 \, x_0^5 x_1^{-7}\right) +/ \left( (1 - x_0 x_1^{-3}) (1 - x_1^2)\right) +$.} +\label{fig:rat} +\end{figure} + +\end{example} + +The whole \rgf/ is represented by a \ai[\tt]{gen\_fun} +structure. +\begin{verbatim} +struct gen_fun { + std::vector< short_rat * > term; + Polyhedron *context; + + void add(ZZ& cn, ZZ& cd, vec_ZZ& num, mat_ZZ& den); + void print(unsigned int nparam, char **param_name); + operator evalue *(); + + gen_fun(Polyhedron *C = NULL) : context(C) {} + ~gen_fun(); +}; +\end{verbatim} +The method \ai[\tt]{gen\_fun::add} adds a new term to the \rgf/. +It makes all powers in the denominator lexico-positive, +orders them in lexicographical order and inserts the new +term in \ai[\tt]{term} according to the lexicographical +order of the combined powers in the denominator. +The method \ai[\tt]{gen\_fun::operator evalue *} performs +the conversion from \rgf/ to \psp/ explained in Section~\ref{s:conversion}. +The \ai[\tt]{Polyhedron} \ai[\tt]{context} is the superset +of all points where the enumerator is non-zero used during this conversion, +i.e., it is the set $Q$ from (\ref{eq:context}). +If \ai[\tt]{context} is \verb+NULL+ the maximal +allowed context is assumed, i.e., the maximal +region with lexico-positive rays. + +\subsection{Counting Functions} +\label{a:counting:functions} + +Our library provides essentially three different counting functions: +one for non-parametric polytopes, one for parametric polytopes +and one for parametric sets with existential variables. + +\begin{verbatim} +void barvinok_count(Polyhedron *P, Value* result, + unsigned NbMaxCons); +\end{verbatim} +The function \ai[\tt]{barvinok\_count} enumerates the non-parametric +polytope \verb+P+ and returns the result in the \ai[\tt]{Value} +pointed to by \verb+result+, which needs to have been allocated +and initialized. +The argument \verb+NbMaxCons+ is passed to various \PolyLib/ +functions and defines the +maximum size of a table used in the double description computation +in the \PolyLib/ function \ai[\tt]{Chernikova}. +In earlier versions of \PolyLib/, +this parameter had to be conservatively set +to a high number to ensure successful operation, +resulting in significant memory overhead. +Our change to allow this table to grow +dynamically is available in recent versions of \PolyLib/. +In these versions, the value no longer indicates the maximal +table size, but rather the size of the initial allocation. +This value may be set to \verb+0+. + +The function \ai[\tt]{barvinok\_enumerate} for enumerating +parametric polytopes was meant to be +a drop-in replacement of \PolyLib/'s \ai[\tt]{Polyhedron\_Enumerate} +function. +Unfortunately, the latter has been changed to +accept an extra argument in recent versions of \PolyLib/ as shown below. +\begin{verbatim} +Enumeration* barvinok_enumerate(Polyhedron *P, Polyhedron* C, + unsigned MaxRays); +extern Enumeration *Polyhedron_Enumerate(Polyhedron *P, + Polyhedron *C, unsigned MAXRAYS, char **pname); +\end{verbatim} +The argument \verb+MaxRays+ has the same meaning as the argument +\verb+NbMaxCons+ above. +The argument \verb+P+ refers to the $(d+n)$-dimensional +polyhedron defining the parametric polytope. +The argument \verb+C+ is an $n$-dimensional polyhedron containing +extra constraints on the parameter space. +Its primary use is to indicate how many of the dimensions +in \verb+P+ refer to parameters as any constraint in \verb+C+ +could equally well have been added to \verb+P+ itself. +Note that the dimensions referring to the parameters should +appear {\em last}. +The result is a newly allocated \ai[\tt]{Enumeration}. +As an alternative we also provide a function +(\ai[\tt]{barvinok\_enumerate\_ev}) that returns +an \ai[\tt]{evalue}. +\begin{verbatim} +evalue* barvinok_enumerate_ev(Polyhedron *P, Polyhedron* C, + unsigned MaxRays); +\end{verbatim} + +For enumerating parametric sets with existentially quantified variables, +we provide two functions: +\ai[\tt]{barvinok\_enumerate\_e} +and +\ai[\tt]{barvinok\_enumerate\_pip}. +\begin{verbatim} +evalue* barvinok_enumerate_e(Polyhedron *P, + unsigned exist, unsigned nparam, unsigned MaxRays); +evalue *barvinok_enumerate_pip(Polyhedron *P, + unsigned exist, unsigned nparam, unsigned MaxRays); +\end{verbatim} +The first function tries the simplification rules from +Section~\ref{s:elimination} before resorting to the method +based on \indac{PIP} from Section~\ref{s:PIP}. +The second function immediately applies the technique from +Section~\ref{s:PIP}. +The argument \verb+exist+ refers to the number of existential variables, +whereas +the argument \verb+nparam+ refers to the number of parameters. +The order of the dimensions in \verb+P+ is: +counted variables first, then existential variables and finally +the parameters. + +The function +\ai[\tt]{barvinok\_series} enumerates parametric polytopes +in the form of a \rgf/. +The polyhedron \verb+P+ is assumed to have only +lexico-positive rays. +\begin{verbatim} +gen_fun * barvinok_series(Polyhedron *P, Polyhedron* C, + unsigned MaxRays); +\end{verbatim} + +\subsection{Auxiliary Functions} + +In this section we briefly mention some auxiliary functions +available in the \barvinok/ library. + +\begin{verbatim} +void Polyhedron_Polarize(Polyhedron *P); +\end{verbatim} +The function \ai[\tt]{Polyhedron\_Polarize} +polarizes its argument and is explained +in Section~\ref{s:computing}. + +\begin{verbatim} +Matrix * unimodular_complete(Vector *row); +\end{verbatim} +The function \ai[\tt]{unimodular\_complete} extends +\verb+row+ to a \ai{unimodular matrix} using the +algorithm of \shortciteN{Bik1996PhD}. + +\begin{verbatim} +int DomainIncludes(Polyhedron *Pol1, Polyhedron *Pol2); +\end{verbatim} +The function \ai[\tt]{DomainIncludes} extends +the function \ai[\tt]{PolyhedronIncludes} +provided by \PolyLib/ +to unions of polyhedra. +It checks whether its first argument is a superset of +its second argument. + +\begin{verbatim} +Polyhedron *DomainConstraintSimplify(Polyhedron *P, + unsigned MaxRays); +\end{verbatim} +The value returned by +\ai[\tt]{DomainConstraintSimplify} is a pointer to +a newly allocated \ai[\tt]{Polyhedron} that contains the +same integer points as its first argument but possibly +has simpler constraints. +Each constraint $ g \sp a x \ge c $ +is replaced by $ \sp a x \ge \ceil{ \frac c g } $, +where $g$ is the \ac{gcd} of the coefficients in the original +constraint. +The \ai[\tt]{Polyhedron} pointed to by \verb+P+ is destroyed. + +\begin{verbatim} +Polyhedron* Polyhedron_Project(Polyhedron *P, int dim); +\end{verbatim} +The function \ai[\tt]{Polyhedron\_Project} projects +\verb+P+ onto its last \verb+dim+ dimensions. + diff --git a/doc/Usage.tex b/doc/Usage.tex new file mode 100644 index 0000000..7d9ae96 --- /dev/null +++ b/doc/Usage.tex @@ -0,0 +1,237 @@ +\section{\texorpdfstring{Usage of the \protect\ai[\tt]{barvinok} library} +{Usage of the barvinok library}} +\label{a:usage} + +\index{barvinok@{\tt barvinok}!availability} +{\sloppy +This section describes some application programs +provided by the \barvinok/ library, +available from {\tt http://freshmeat.net/projects/barvinok/.} +For compilation instructions we refer to the \verb+README+ file +included in the distribution. +} + +The program \ai[\tt]{barvinok\_count} enumerates a +non-parametric polytope. It takes one polytope +in \PolyLib/ notation as input and prints the number +of integer points in the polytope and the time taken +by both ``manual counting'' and Barvinok's method. +The \PolyLib/ notation corresponds to the internal +representation of \ai[\tt]{Polyhedron}s as explained +in Appendix~\ref{a:existing}. +The first line of the input contains the number of rows +and the number of columns in the \ai[\tt]{Constraint} matrix. +The rest of the input is composed of the elements of the matrix. +Recall that the number of columns is two more than the number +of variables, where the extra first columns is one or zero +depending on whether the constraint is an inequality ($\ge 0$) +or an equality ($= 0$). The next columns contain +the coefficients of the variables and the final column contains +the constant in the constraint. +E.g., the set +$S = \lb\, s \mid s \geq 0 \wedge 2 s \leq 13 \, \rb$ +from Example~\pref{ex:S:7} corresponds to the following input and +output. +\begin{verbatim} +> cat S +2 3 + +1 1 0 +1 -2 13 +> ./barvinok_count < S +POLYHEDRON Dimension:1 + Constraints:2 Equations:0 Rays:2 Lines:0 +Constraints 2 3 +Inequality: [ 1 0 ] +Inequality: [ -2 13 ] +Rays 2 3 +Vertex: [ 0 ]/1 +Vertex: [ 13 ]/2 +manual: 7 +User: 0.01; Sys: 0 +Barvinok: 7 +User: 0; Sys: 0 +\end{verbatim} +The program \ai[\tt]{cdd2polylib.pl} can be used to +convert a polytope from \ai[\tt]{cdd} \shortcite{cdd} +notation to \PolyLib/ notation. + +The program \ai[\tt]{barvinok\_enumerate} enumerates a +parametric polytope. It takes two polytopes in \PolyLib/ +notation as input, optionally followed by a list of parameter +names. +The two polytopes refer to arguments \verb+P+ and \verb+C+ +of the corresponding function. (See Appendix~\ref{a:counting:functions}.) +The following example was taken by \shortciteN{Loechner1999} +from \shortciteN[Chapter II.2]{Loechner97phd}. +\begin{verbatim} +> cat loechner +# Dimension of the matrix: +7 7 +# Constraints: +# i j k P Q cte +1 1 0 0 0 0 0 # 0 <= i +1 -1 0 0 1 0 0 # i <= P +1 0 1 0 0 0 0 # 0 <= j +1 1 -1 0 0 0 0 # j <= i +1 0 0 1 0 0 0 # 0 <= k +1 1 -1 -1 0 0 0 # k <= i-j +0 1 1 1 0 -1 0 # Q = i + j + k + +# 2 parameters, no constraints. +0 4 +> ./barvinok_enumerate < loechner +POLYHEDRON Dimension:5 + Constraints:6 Equations:1 Rays:5 Lines:0 +Constraints 6 7 +Equality: [ 1 1 1 0 -1 0 ] +Inequality: [ 0 1 1 1 -1 0 ] +Inequality: [ 0 1 0 0 0 0 ] +Inequality: [ 0 0 1 0 0 0 ] +Inequality: [ 0 -2 -2 0 1 0 ] +Inequality: [ 0 0 0 0 0 1 ] +Rays 5 7 +Ray: [ 1 0 1 1 2 ] +Ray: [ 1 1 0 1 2 ] +Vertex: [ 0 0 0 0 0 ]/1 +Ray: [ 0 0 0 1 0 ] +Ray: [ 1 0 0 1 1 ] +POLYHEDRON Dimension:2 + Constraints:1 Equations:0 Rays:3 Lines:2 +Constraints 1 4 +Inequality: [ 0 0 1 ] +Rays 3 4 +Line: [ 1 0 ] +Line: [ 0 1 ] +Vertex: [ 0 0 ]/1 + - P + Q >= 0 + 2P - Q >= 0 + 1 >= 0 + +( -1/2 * P^2 + ( 1 * Q + 1/2 ) + * P + ( -3/8 * Q^2 + ( -1/2 * {( 1/2 * Q + 0 ) +} + 1/4 ) + * Q + ( -5/4 * {( 1/2 * Q + 0 ) +} + 1 ) + ) + ) + Q >= 0 + P - Q -1 >= 0 + 1 >= 0 + +( 1/8 * Q^2 + ( -1/2 * {( 1/2 * Q + 0 ) +} + 3/4 ) + * Q + ( -5/4 * {( 1/2 * Q + 0 ) +} + 1 ) + ) +\end{verbatim} +The output corresponds to +$$ +\begin{cases} +\makebox[0pt][l]{$-\frac 1 2 P^2 + P Q + \frac 1 2 P - \frac 3 8 Q^2 ++ \left( \frac 1 4 - \frac 1 2 \left\{ \frac 1 2 Q \right\} \right) + Q + 1 +- \frac 5 4 \left\{ \frac 1 2 Q \right\}$} \\ +& +\hbox{if $P \le Q \le 2 P$} +\\ +\frac 1 8 Q^2 + +\left( \frac 3 4 - \frac 1 2 \left\{ \frac 1 2 Q \right\} \right) +- \frac 5 4 \left\{ \frac 1 2 Q \right\} +\qquad +\qquad +\qquad +\qquad +\qquad +& +\hbox{if $0 \le Q \le P-1$} +. +\end{cases} +$$ + +The program \ai[\tt]{barvinok\_enumerate\_e} enumerates a +parametric projected set. It takes a single polytopes in \PolyLib/ +notation as input, followed by two lines indicating the number +or existential variables and the number of parameters and +optionally followed by a list of parameter names. +The syntax for the line indicating the number of existential +variables is the letter \verb+E+ followed by a space and the actual number. +For indicating the number of parameters, the letter \verb+P+ is used. +The following example corresponds to Example~\pref{ex:S}. +\begin{verbatim} +> cat projected +5 6 +# k i j p cst +1 0 1 0 0 -1 +1 0 -1 0 0 8 +1 0 0 1 0 -1 +1 0 0 -1 1 0 +0 -1 6 9 0 -7 + +E 2 +P 1 +> ./barvinok_enumerate_e = 0 + 1 >= 0 + +( 3 * P + 10 ) + P -1 >= 0 + - P + 2 >= 0 + +( 8 * P + 0 ) +\end{verbatim} + +The program \ai[\tt]{barvinok\_series} enumerates a +parametric polytope in the form of a \rgf/. +The input of this program is the same as that of +\ai[\tt]{barvinok\_enumerate}, except that the input polyhedron +is assumed to be full-dimensional. +The following is an example of Petr Lison\u{e}k\index{Lison\u{e}k, P.}. +\begin{verbatim} +> cat petr +4 6 +1 -1 -1 -1 1 0 +1 1 -1 0 0 0 +1 0 1 -1 0 0 +1 0 0 1 0 -1 + +0 3 +n +> ./barvinok_series < petr +POLYHEDRON Dimension:4 + Constraints:5 Equations:0 Rays:5 Lines:0 +Constraints 5 6 +Inequality: [ -1 -1 -1 1 0 ] +Inequality: [ 1 -1 0 0 0 ] +Inequality: [ 0 1 -1 0 0 ] +Inequality: [ 0 0 1 0 -1 ] +Inequality: [ 0 0 0 0 1 ] +Rays 5 6 +Ray: [ 1 1 1 3 ] +Ray: [ 1 1 0 2 ] +Ray: [ 1 0 0 1 ] +Ray: [ 0 0 0 1 ] +Vertex: [ 1 1 1 3 ]/1 +POLYHEDRON Dimension:1 + Constraints:1 Equations:0 Rays:2 Lines:1 +Constraints 1 3 +Inequality: [ 0 1 ] +Rays 2 3 +Line: [ 1 ] +Vertex: [ 0 ]/1 +(n^3)/((1-n) * (1-n) * (1-n^2) * (1-n^3)) +\end{verbatim} diff --git a/doc/barvinok.bib b/doc/barvinok.bib new file mode 100644 index 0000000..2f960ac --- /dev/null +++ b/doc/barvinok.bib @@ -0,0 +1,83 @@ +@string(ICPS = "ICPS, Universit\'e Louis Pasteur de Strasbourg, France") + +@techreport{ Wilde1993, + author = "D. K. Wilde", + title = "A Library for doing polyhedral operations", + number = "785", + institution = "IRISA, Rennes, France", + pages = "45 p.", + year = 1993, + url = "citeseer.nj.nec.com/article/wilde93library.html", + note = "\\http://www.irisa.fr/EXTERNE/bibli/pi/pi785.html" +} + +@article{ Loechner97parameterized, + author = "Vincent Loechner and Doran K. Wilde", + title = "Parameterized Polyhedra and Their Vertices", + journal = "International Journal of Parallel Programming", + volume = "25", + number = "6", + pages = "525--549", + year = "1997", + month = dec, + publisher = {Kluwer Academic Publishers}, + url = "citeseer.nj.nec.com/article/loechner95parameterized.html" } + +@TechReport{ Loechner1999, + author = "Vincent Loechner", + month = mar, + year = 1999, + title = "PolyLib: A Library for Manipulating Parameterized Polyhedra", + institution = ICPS, +} + +@article{ Clauss1998parametric, + author = "Clauss, Philippe and Loechner, Vincent", + title = "Parametric analysis of polyhedral iteration spaces", + journal = "Journal of {VLSI} Signal Processing", + publisher = "Kluwer Academic Publishers, Boston", + year = "1998", + volume = 19, + pages = "179--194", + number = 2, + month = jul, +} + +@mastersthesis{ Seghir2002, + title = {D\'enombrement des Point Entiers de l'Union et de + l'Image des Poly\'edres Param\'etr\'es}, + author = "Rachid Seghir", + month = jun, + school = ICPS, + year = 2002, +} + +@techreport{cdd, + author = "K. Fukuda", + title = "cdd.c: C-implementation of the double description method for computing all vertices and extremal rays of a convex polyhedron given by a system of linear inequalities", + institution = "Department of Mathematics, Swiss Federal Institute of Technology, Lausanne, Switzerland", + year = 1993, + note = "program available from http://www.ifor.math.ethz.ch/~fukuda/fukuda.html", +} + +@PhdThesis{Loechner97phd, + author = "V. Loechner", + title = {Contribution \`a l'\'etude des poly\`edres +param\'etr\'es et applications en parall\'elisation automatique}, + school = "University Louis Pasteur, Strasbourg", + year = 1997, +} + +@PHDTHESIS{ Bik1996PhD, + AUTHOR = {A. J. C. Bik}, + TITLE = {Compiler Support for Sparse Matrix Computations}, + SCHOOL = {University of Leiden}, + ADDRESS = {The Netherlands}, + YEAR = {1996}, + ISBN = {}, + NOTE = {}, + CONTENTS = {}, + sourceURL = {ftp://ftp.wi.leidenuniv.nl/pub/CS/PhDTheses/bik-96.ps.gz}, + FLAGS = {own}, + TOPICS = {Sparse Arrays} +} diff --git a/doc/barvinok.gdf b/doc/barvinok.gdf new file mode 100644 index 0000000..0b9c5a0 --- /dev/null +++ b/doc/barvinok.gdf @@ -0,0 +1,65 @@ +@entry{DAG, DAG, Directed Acyclic Graph} +@entry{HNF, HNF, Hermite Normal Form} +@entry{IG, IG, Interference Graph} +@entry{ILPa, ILP, Instruction-Level Parallelism} +@entry{ILPr, ILP, Integer Linear Programming} +@entry{SG, SG, Spanning Graph} +@entry{LCG, LCG, Loop Communication Graph} +@entry{LDG, LDG, Loop Dependence Graph} +@entry{ADG, ADG, Apparent Dependence Graph} +@entry{EDG, EDG, Expanded Dependence Graph} +@entry{RDG, RDG, Reduced Dependence Graph} +@entry{SCC, SCC, strongly connected component} +@entry{gcd, gcd, greatest common divisor} +@entry{lcm, lcm, least common multiple} +@entry{CARE, CARE, Conditional Affine Recurrence Equations} +@entry{SARE, SARE, System of Affine Recurrence Equations} +@entry{SURE, SURE, System of Uniform Recurrence Equations} +@entry{PLS, PLS, piecewise-linear schedule} +@entry{VDLS, VDLS, variable dependent linear schedule} +@entry{APP, APP, Algebraic Path Problem} +@entry{PRDG, PRDG, polyhedral reduced dependence graph} +@entry{RecMII, RecMII, Recurrence Minimum Initiation Interval} +@entry{ResMII, ResMII, Resource Minimum Initiation Interval} +@entry{SDF, SDF, Synchronous Dataflow} +@entry{CBP, CBP, consumed-before-produced} +@entry{HLL, HLL, High Level Language} +@entry{CSP, CSP, Communicating Sequential Processes} +@entry{AST, AST, Abstract Syntax Tree} +@entry{LLL, LLL, Lenstra, Lenstra and Lovasz' basis reduction algorithm} +@entry{DSA, DSA, Dynamic Single Assignment} +@entry{CME, CME, Cache Miss Equations} +@entry{PME, PME, Probabilistic Miss Equations} +@entry{WCET, WCET, Worst-Case Execution Time} +@entry{TLB, TLB, Translation Lookaside Buffer} +@entry{NDD, NDD, Number Decision Diagram} +@entry{DFA, DFA, Deterministic Finite Automaton} +@entry{LSB, LSB, Least Significant Bit} +@entry{MSB, MSB, Most Significant Bit} +@entry{FSA, FSA, Finite State Automaton} +@entry{WS1S, WS1S, Weak Second-order Theory of One Successor} +@entry{lub, lub, least upper bound} +@entry{CAD, CAD, Cylindrical Algebraic Decomposition} +@entry{PER, {\tt PER}, Polyhedral Extraction Routine} +@entry{W2P, {\tt W2P}, WHIRL to Polyhedra} +@entry{ORC, {\tt ORC}, Open Research Compiler} +@entry{pers, {\tt pers}, PER in SUIF} +@entry{DTSE, DTSE, Data Transfer and Storage Exploration} +@entry{SUIF, SUIF, Stanford University Intermediate Format} +@entry{s2c, s2c, SUIF to C} +@entry{cloog, {\tt CLooG}, Chunky Loop Generator} +@entry{wloog, {\tt WLooG}, WHIRL Loop Generator} +@entry{sloog, {\tt sloog}, SUIF Loop Generator} +@entry{USVD, USVD, Updating Singular Value Decomposition} +@entry{SCBD, SCBD, Storage Cycle Budget Distribution} +@entry{MHLA, MHLA, Memory Hierarchy Layer Assignment} +@entry{BG, BG, Basic Group} +@entry{SBO, SBO, Storage Bandwidth Optimization)} +@entry{MC, MC, Memory Compaction} +@entry{CD, CD, Cavity Detection} +@entry{BRD, BRD, Backward Reuse Distance} +@entry{RACE, RACE, Reduction of Arithmetic Cost of Expressions} +@entry{PIP, PIP, Parametric Integer Programming} +@entry{ADS, ADS, Accessed Data Set} +@entry{OOM, OOM, Out Of Memory} +@entry{LBL, LBL, Linearly Bounded Lattice} diff --git a/doc/barvinok.tex b/doc/barvinok.tex new file mode 100644 index 0000000..cf6b661 --- /dev/null +++ b/doc/barvinok.tex @@ -0,0 +1,26 @@ +\documentclass[10pt,dvips,openbib]{article} +\usepackage{makeidx} +\usepackage[all,web,line,arc,tile,color]{xy} +\usepackage[plainpages=false,pdfpagelabels,breaklinks,pagebackref]{hyperref} +\usepackage{mydefs} +\usepackage{chicago} + +\makeglossary +\makeindex + +\begin{document} + +\include{Internal} + +\include{Usage} + +\bibliography{barvinok} +\bibliographystyle{chicago} + +\index{index|(} + +\printindex + +\index{index|)} + +\end{document} diff --git a/doc/chicago.bst b/doc/chicago.bst new file mode 100644 index 0000000..ba05833 --- /dev/null +++ b/doc/chicago.bst @@ -0,0 +1,1726 @@ +%%% ==================================================================== +%%% @BibTeX-style-file{ +%%% author = "Glenn Paulley", +%%% version = "4", +%%% date = "28 August 1992", +%%% time = "10:23:39 199", +%%% filename = "chicago.bst", +%%% address = "Data Structuring Group +%%% Department of Computer Science +%%% University of Waterloo +%%% Waterloo, Ontario, Canada +%%% N2L 3G1", +%%% telephone = "(519) 885-1211", +%%% FAX = "(519) 885-1208", +%%% checksum = "26323 1654 5143 37417", +%%% email = "gnpaulle@bluebox.uwaterloo.ca", +%%% codetable = "ISO/ASCII", +%%% keywords = "", +%%% supported = "yes", +%%% abstract = "A BibTeX bibliography style that follows the +%%% `B' reference style of the 13th Edition of +%%% the Chicago Manual of Style. A detailed +%%% feature list is given below.", +%%% docstring = "The checksum field above contains a CRC-16 +%%% checksum as the first value, followed by the +%%% equivalent of the standard UNIX wc (word +%%% count) utility output of lines, words, and +%%% characters. This is produced by Robert +%%% Solovay's checksum utility.", +%%% } +%%% ==================================================================== +% +% "Chicago" BibTeX style, chicago.bst +% =================================== +% +% BibTeX `chicago' style file for BibTeX version 0.99c, LaTeX version 2.09 +% Place it in a file called chicago.bst in the BibTeX search path. +% You need to include chicago.sty as a \documentstyle option. +% (Placing it in the same directory as the LaTeX document should also work.) +% This "chicago" style is based on newapa.bst (American Psych. Assoc.) +% found at ymir.claremont.edu. +% +% Citation format: (author-last-name year) +% (author-last-name and author-last-name year) +% (author-last-name, author-last-name, and author-last-name year) +% (author-last-name et al. year) +% (author-last-name) +% author-last-name (year) +% (author-last-name and author-last-name) +% (author-last-name et al.) +% (year) or (year,year) +% year or year,year +% +% Reference list ordering: alphabetical by author or whatever passes +% for author in the absence of one. +% +% This BibTeX style has support for abbreviated author lists and for +% year-only citations. This is done by having the citations +% actually look like +% +% \citeauthoryear{full-author-info}{abbrev-author-info}{year} +% +% The LaTeX style has to have the following (or similar) +% +% \let\@internalcite\cite +% \def\fullcite{\def\citeauthoryear##1##2##3{##1, ##3}\@internalcite} +% \def\fullciteA{\def\citeauthoryear##1##2##3{##1}\@internalcite} +% \def\shortcite{\def\citeauthoryear##1##2##3{##2, ##3}\@internalcite} +% \def\shortciteA{\def\citeauthoryear##1##2##3{##2}\@internalcite} +% \def\citeyear{\def\citeauthoryear##1##2##3{##3}\@internalcite} +% +% These TeX macro definitions are found in chicago.sty. Additional +% commands to manipulate different components of a citation can be defined +% so that, for example, you can list author's names without parentheses +% if using a citation as a noun or object in a sentence. +% +% This file was originally copied from newapa.bst at ymir.claremont.edu. +% +% Features of chicago.bst: +% ======================= +% +% - full names used in citations, but abbreviated citations are available +% (see above) +% - if an entry has a "month", then the month and year are also printed +% as part of that bibitem. +% - all conjunctions use "and" instead of "\&" +% - major modification from Chicago Manual of Style (13th ed.) is that +% only the first author in a reference appears last name first- +% additional authors appear as J. Q. Public. +% - pages are listed as "pp. xx-xx" in all entry types except +% article entries. +% - book, inbook, and manual use "location: publisher" (or organization) +% for address and publisher. All other types list publishers separately. +% - "pp." are used to identify page numbers for all entry types except +% articles. +% - organization is used as a citation label if neither author nor editor +% is present (for manuals). +% - "et al." is used for long author and editor lists, or when "others" +% is used. +% +% Modifications and bug fixes from newapa.bst: +% =========================================== +% +% - added month, year to bib entries if month is present +% - fixed bug with In proceedings, added necessary comma after title +% - all conjunctions changed to "and" from "\&" +% - fixed bug with author labels in my.full.label: "et al." now is +% generated when "others" is an author name +% - major modification from Chicago Manual of Style (13th ed.) is that +% only the first author in a reference appears last name first- +% additional authors appear as J. Q. Public. +% - pages are listed as "pp. xx-xx" in all entry types except +% article entries. Unnecessary (IMHO) "()" around page numbers +% were removed, and page numbers now don't end with a period. +% - created chicago.sty for use with this bibstyle (required). +% - fixed bugs in FUNCTION {format.vol.num.pages} for missing volume, +% number, and /or pages. Renamed to format.jour.vol. +% - fixed bug in formatting booktitles: additional period an error if +% book has a volume. +% - fixed bug: editors usually given redundant period before next clause +% (format.editors.dot) removed. +% - added label support for organizations, if both author and editor +% are missing (from alpha.bst). If organization is too long, then +% the key field is used for abbreviated citations. +% - In proceedings or books of several volumes, no comma was written +% between the "Volume x" and the page numbers (this was intentional +% in newapa.bst). Fixed. +% - Some journals may not have volumes/numbers, only month/year (eg. +% IEEE Computer). Fixed bug in article style that assumed volume/number +% was always present. +% +% Original documentation for newapa.sty: +% ===================================== +% +% This version was made by modifying the master file made by +% Oren Patashnik (PATASHNIK@SCORE.STANFORD.EDU), and the 'named' BibTeX +% style of Peter F. Patel-Schneider. +% +% Copyright (C) 1985, all rights reserved. +% Copying of this file is authorized only if either +% (1) you make absolutely no changes to your copy, including name, or +% (2) if you do make changes, you name it something other than 'newapa.bst'. +% There are undoubtably bugs in this style. If you make bug fixes, +% improvements, etc. please let me know. My e-mail address is: +% spencer@cgrg.ohio.state.edu or 71160.3141@compuserve.com +% +% This style was made from 'plain.bst', 'named.bst', and 'apalike.bst', +% with lots of tweaking to make it look like APA style, along with tips +% from Young Ryu and Brian Reiser's modifications of 'apalike.bst'. + +ENTRY + { address + author + booktitle + chapter + edition + editor + fjournal + howpublished + institution + journal + key + month + note + number + organization + pages + publisher + school + series + title + type + volume + year + } + {} + { label.year extra.label sort.year sort.label } + +INTEGERS { output.state before.all mid.sentence after.sentence after.block } + +FUNCTION {init.state.consts} +{ #0 'before.all := + #1 'mid.sentence := + #2 'after.sentence := + #3 'after.block := +} + +STRINGS { s t u } + +FUNCTION {output.nonnull} +{ 's := + output.state mid.sentence = + { ", " * write$ } + { output.state after.block = + { add.period$ write$ + newline$ + "\newblock " write$ + } + { output.state before.all = + 'write$ + { add.period$ " " * write$ } + if$ + } + if$ + mid.sentence 'output.state := + } + if$ + s +} + +% Use a colon to separate output. Used only for address/publisher +% combination in book/inbook types, address/institution for manuals, +% and organization:publisher for proceedings (inproceedings). +% +FUNCTION {output.nonnull.colon} +{ 's := + output.state mid.sentence = + { ": " * write$ } + { output.state after.block = + { add.period$ write$ + newline$ + "\newblock " write$ + } + { output.state before.all = + 'write$ + { add.period$ " " * write$ } + if$ + } + if$ + mid.sentence 'output.state := + } + if$ + s +} + +FUNCTION {output} +{ duplicate$ empty$ + 'pop$ + 'output.nonnull + if$ +} + +FUNCTION {output.colon} +{ duplicate$ empty$ + 'pop$ + 'output.nonnull.colon + if$ +} + +FUNCTION {output.check} +{ 't := + duplicate$ empty$ + { pop$ "empty " t * " in " * cite$ * warning$ } + 'output.nonnull + if$ +} + +FUNCTION {output.check.colon} +{ 't := + duplicate$ empty$ + { pop$ "empty " t * " in " * cite$ * warning$ } + 'output.nonnull.colon + if$ +} + +FUNCTION {output.year.check} +{ year empty$ + { "empty year in " cite$ * warning$ } + { write$ + " (" year * extra.label * + month empty$ + { ")" * } + { ", " * month * ")" * } + if$ + mid.sentence 'output.state := + } + if$ +} + + +FUNCTION {fin.entry} +{ add.period$ + write$ + newline$ +} + +FUNCTION {new.block} +{ output.state before.all = + 'skip$ + { after.block 'output.state := } + if$ +} + +FUNCTION {new.sentence} +{ output.state after.block = + 'skip$ + { output.state before.all = + 'skip$ + { after.sentence 'output.state := } + if$ + } + if$ +} + +FUNCTION {not} +{ { #0 } + { #1 } + if$ +} + +FUNCTION {and} +{ 'skip$ + { pop$ #0 } + if$ +} + +FUNCTION {or} +{ { pop$ #1 } + 'skip$ + if$ +} + +FUNCTION {new.block.checka} +{ empty$ + 'skip$ + 'new.block + if$ +} + +FUNCTION {new.block.checkb} +{ empty$ + swap$ empty$ + and + 'skip$ + 'new.block + if$ +} + +FUNCTION {new.sentence.checka} +{ empty$ + 'skip$ + 'new.sentence + if$ +} + +FUNCTION {new.sentence.checkb} +{ empty$ + swap$ empty$ + and + 'skip$ + 'new.sentence + if$ +} + +FUNCTION {field.or.null} +{ duplicate$ empty$ + { pop$ "" } + 'skip$ + if$ +} + +% +% Emphasize the top string on the stack. +% +FUNCTION {emphasize} +{ duplicate$ empty$ + { pop$ "" } + { "{\em " swap$ * "}" * } + if$ +} + +% +% Emphasize the top string on the stack, but add a trailing space. +% +FUNCTION {emphasize.space} +{ duplicate$ empty$ + { pop$ "" } + { "{\em " swap$ * "\/}" * } + if$ +} + +INTEGERS { nameptr namesleft numnames } +% +% Format bibliographical entries with the first author last name first, +% and subsequent authors with initials followed by last name. +% All names are formatted in this routine. +% +FUNCTION {format.names} +{ 's := + #1 'nameptr := % nameptr = 1; + s num.names$ 'numnames := % numnames = num.name$(s); + numnames 'namesleft := + { namesleft #0 > } + + { nameptr #1 = + {s nameptr "{vv~}{ll}{, jj}{, f.}" format.name$ 't := } + {s nameptr "{f.~}{vv~}{ll}{, jj}" format.name$ 't := } + if$ + nameptr #1 > + { namesleft #1 > + { ", " * t * } + { numnames #2 > + { "," * } + 'skip$ + if$ + t "others" = + { " et~al." * } + { " and " * t * } % from Chicago Manual of Style + if$ + } + if$ + } + 't + if$ + s nameptr "{vv~}{ll}{, jj}{, f.}" format.name$ 't := + "\protect \index {" * t * "|hyperemph}" * + nameptr #1 + 'nameptr := % nameptr += 1; + namesleft #1 - 'namesleft := % namesleft =- 1; + } + while$ +} + +FUNCTION {my.full.label} +{ 's := + #1 'nameptr := % nameptr = 1; + s num.names$ 'numnames := % numnames = num.name$(s); + numnames 'namesleft := + { namesleft #0 > } + + { s nameptr "{vv~}{ll}" format.name$ 't := % get the next name + nameptr #1 > + { namesleft #1 > + { ", " * t * } + { numnames #2 > + { "," * } + 'skip$ + if$ + t "others" = + { " et~al." * } + { " and " * t * } % from Chicago Manual of Style + if$ + } + if$ + } + 't + if$ + s nameptr "{vv~}{ll}{, jj}{, f.}" format.name$ 't := + "\protect \index {" * t * "|bold}" * + nameptr #1 + 'nameptr := % nameptr += 1; + namesleft #1 - 'namesleft := % namesleft =- 1; + } + while$ + +} + +FUNCTION {format.names.fml} +% +% Format names in "familiar" format, with first initial followed by +% last name. Like format.names, ALL names are formatted. +% +{ 's := + #1 'nameptr := % nameptr = 1; + s num.names$ 'numnames := % numnames = num.name$(s); + numnames 'namesleft := + { namesleft #0 > } + + { s nameptr "{f.~}{vv~}{ll}{, jj}" format.name$ 't := + + nameptr #1 > + { namesleft #1 > + { ", " * t * } + { numnames #2 > + { "," * } + 'skip$ + if$ + t "others" = + { " et~al." * } + { " and " * t * } +% { " \& " * t * } + if$ + } + if$ + } + 't + if$ + nameptr #1 + 'nameptr := % nameptr += 1; + namesleft #1 - 'namesleft := % namesleft =- 1; + } + while$ +} + +FUNCTION {format.authors} +{ author empty$ + { "" } + { author format.names } + if$ +} + +FUNCTION {format.key} +{ empty$ + { key field.or.null } + { "" } + if$ +} + +% +% Format editor names for use in the "in" types: inbook, incollection, +% inproceedings: first initial, then last names. When editors are the +% LABEL for an entry, then format.editor is used which lists editors +% by last name first. +% +FUNCTION {format.editors.fml} +{ editor empty$ + { "" } + { editor format.names.fml + editor num.names$ #1 > + { " (Eds.)" * } + { " (Ed.)" * } + if$ + } + if$ +} + +% +% Format editor names for use in labels, last names first. +% +FUNCTION {format.editors} +{ editor empty$ + { "" } + { editor format.names + editor num.names$ #1 > + { " (Eds.)" * } + { " (Ed.)" * } + if$ + } + if$ +} + +FUNCTION {format.title} +{ title empty$ + { "" } + { title "t" change.case$ } + if$ +} + +% Note that the APA style requres case changes +% in article titles. The following does not +% change cases. If you perfer it, uncomment the +% following and comment out the above. + +%FUNCTION {format.title} +%{ title empty$ +% { "" } +% { title } +% if$ +%} + +FUNCTION {n.dashify} +{ 't := + "" + { t empty$ not } + { t #1 #1 substring$ "-" = + { t #1 #2 substring$ "--" = not + { "--" * + t #2 global.max$ substring$ 't := + } + { { t #1 #1 substring$ "-" = } + { "-" * + t #2 global.max$ substring$ 't := + } + while$ + } + if$ + } + { t #1 #1 substring$ * + t #2 global.max$ substring$ 't := + } + if$ + } + while$ +} + +FUNCTION {format.btitle} +{ edition empty$ + { title emphasize } + { title empty$ + { title emphasize } + { volume empty$ % gnp - check for volume, then don't need period + { "{\em " title * "\/} (" * edition * " ed.)" * "." * } + { "{\em " title * "\/} (" * edition * " ed.)" * } + if$ + } + if$ + } + if$ +} + +FUNCTION {format.emphasize.booktitle} +{ edition empty$ + { booktitle emphasize } + { booktitle empty$ + { booktitle emphasize } + { volume empty$ % gnp - extra period an error if book has a volume + { "{\em " booktitle * "\/} (" * edition * " ed.)" * "." *} + { "{\em " booktitle * "\/} (" * edition * " ed.)" * } + if$ + } + if$ + } + if$ + } + + +FUNCTION {tie.or.space.connect} +{ duplicate$ text.length$ #3 < + { "~" } + { " " } + if$ + swap$ * * +} + +FUNCTION {either.or.check} +{ empty$ + 'pop$ + { "can't use both " swap$ * " fields in " * cite$ * warning$ } + if$ +} + +FUNCTION {format.bvolume} +{ volume empty$ + { "" } + { "Volume" volume tie.or.space.connect % gnp - changed to mixed case + series empty$ + 'skip$ + { " of " * series emphasize * } + if$ + "volume and number" number either.or.check + } + if$ +} + +FUNCTION {format.number.series} +{ volume empty$ + { number empty$ + { series field.or.null } + { output.state mid.sentence = + { "Number" } % gnp - changed to mixed case always + { "Number" } + if$ + number tie.or.space.connect + series empty$ + { "there's a number but no series in " cite$ * warning$ } + { " in " * series * } + if$ + } + if$ + } + { "" } + if$ +} + +INTEGERS { multiresult } + +FUNCTION {multi.page.check} +{ 't := + #0 'multiresult := + { multiresult not + t empty$ not + and + } + { t #1 #1 substring$ + duplicate$ "-" = + swap$ duplicate$ "," = + swap$ "+" = + or or + { #1 'multiresult := } + { t #2 global.max$ substring$ 't := } + if$ + } + while$ + multiresult +} + +FUNCTION {format.pages} +{ pages empty$ + { "" } + { pages multi.page.check + { "pp.\ " pages n.dashify tie.or.space.connect } % gnp - removed () + { "pp.\ " pages tie.or.space.connect } + if$ + } + if$ +} + +% By Young (and Spencer) +% GNP - fixed bugs with missing volume, number, and/or pages +% +% Format journal, volume, number, pages for article types. +% +FUNCTION {format.jour.vol} +{ fjournal empty$ + { journal empty$ + { "no journal in " cite$ * warning$ + "" } + { journal emphasize.space } + if$ + } + { fjournal emphasize.space } + if$ + number empty$ + { volume empty$ + { "no number and no volume in " cite$ * warning$ + "" * } + { "~{\em " * Volume * "}" * } + if$ + } + { volume empty$ + {"no volume for " cite$ * warning$ + "~(" * number * ")" * } + { "~" * + volume emphasize.space + "(" * number * ")" * * } + if$ + } + if$ + pages empty$ + {"page numbers missing in " cite$ * warning$ + "" * } % gnp - place a null string on the stack for output + { duplicate$ empty$ + { pop$ format.pages } + { ", " * pages n.dashify * } % gnp - removed pp. for articles + if$ + } + if$ +} + +FUNCTION {format.chapter.pages} +{ chapter empty$ + 'format.pages + { type empty$ + { "Chapter" } % gnp - changed to mixed case + { type "t" change.case$ } + if$ + chapter tie.or.space.connect + pages empty$ + {"page numbers missing in " cite$ * warning$} % gnp - added check + { ", " * format.pages * } + if$ + } + if$ +} + +FUNCTION {format.in.ed.booktitle} +{ booktitle empty$ + { "" } + { editor empty$ + { "In " format.emphasize.booktitle * } + { "In " format.editors.fml * ", " * format.emphasize.booktitle * } + if$ + } + if$ +} + +FUNCTION {format.thesis.type} +{ type empty$ + 'skip$ + { pop$ + type "t" change.case$ + } + if$ +} + +FUNCTION {format.tr.number} +{ type empty$ + { "Technical Report" } + 'type + if$ + number empty$ + { "t" change.case$ } + { number tie.or.space.connect } + if$ +} + +FUNCTION {format.article.crossref} +{ "See" + "\citeN{" * crossref * "}" * +} + +FUNCTION {format.crossref.editor} +{ editor #1 "{vv~}{ll}" format.name$ + editor num.names$ duplicate$ + #2 > + { pop$ " et~al." * } + { #2 < + 'skip$ + { editor #2 "{ff }{vv }{ll}{ jj}" format.name$ "others" = + { " et~al." * } + { " and " * editor #2 "{vv~}{ll}" format.name$ * } + if$ + } + if$ + } + if$ +} + +FUNCTION {format.book.crossref} +{ volume empty$ + { "empty volume in " cite$ * "'s crossref of " * crossref * warning$ + "In " + } + { "Volume" volume tie.or.space.connect % gnp - changed to mixed case + " of " * + } + if$ + editor empty$ + editor field.or.null author field.or.null = + or + { key empty$ + { series empty$ + { "need editor, key, or series for " cite$ * " to crossref " * + crossref * warning$ + "" * + } + { "{\em " * series * "\/}" * } + if$ + } + { key * } + if$ + } + { format.crossref.editor * } + if$ + " \citeN{" * crossref * "}" * +} + +FUNCTION {format.incoll.inproc.crossref} +{ "See" + " \citeN{" * crossref * "}" * +} + +% format.lab.names: +% +% determines "short" names for the abbreviated author information. +% "Long" labels are created in calc.label, using the routine my.full.label +% to format author and editor fields. +% +% There are 4 cases for labels. (n=3 in the example) +% a) one author Foo +% b) one to n Foo, Bar and Baz +% c) use of "and others" Foo, Bar et al. +% d) more than n Foo et al. +% +FUNCTION {format.lab.names} +{ 's := + s num.names$ 'numnames := + numnames #2 > % change number to number of others allowed before + % forcing "et al". + { s #1 "{vv~}{ll}" format.name$ + "\protect \index {" * + s #1 "{vv~}{ll}{, jj}{, f.}" format.name$ * + "}" * + "\protect\chicagoetal/" * } + { + numnames #1 - 'namesleft := + #2 'nameptr := + s #1 "{vv~}{ll}" format.name$ + "\protect \index {" * + s #1 "{vv~}{ll}{, jj}{, f.}" format.name$ * + "}" * + { namesleft #0 > } + { nameptr numnames = + { s nameptr "{ff }{vv }{ll}{ jj}" format.name$ "others" = + { "\protect\chicagoetal/" * } + { "\protect\chicagoand/" * s nameptr "{vv~}{ll}" format.name$ * + "\protect \index {" * + s nameptr "{vv~}{ll}{, jj}{, f.}" format.name$ * + "}" * + } + if$ + } + { ", " * s nameptr "{vv~}{ll}" format.name$ * } + if$ + nameptr #1 + 'nameptr := + namesleft #1 - 'namesleft := + } + while$ + } + if$ +} + +FUNCTION {author.key.label} +{ author empty$ + { key empty$ + { "no key, author in " cite$ * warning$ + cite$ #1 #3 substring$ } + 'key + if$ + } + { author format.lab.names } + if$ +} + +FUNCTION {editor.key.label} +{ editor empty$ + { key empty$ + { "no key, editor in " cite$ * warning$ + cite$ #1 #3 substring$ } + 'key + if$ + } + { editor format.lab.names } + if$ +} + +FUNCTION {author.key.organization.label} +% +% added - gnp. Provide label formatting by organization if author is null. +% +{ author empty$ + { organization empty$ + { key empty$ + { "no key, author or organization in " cite$ * warning$ + cite$ #1 #3 substring$ } + 'key + if$ + } + { organization } + if$ + } + { author format.lab.names } + if$ +} + +FUNCTION {editor.key.organization.label} +% +% added - gnp. Provide label formatting by organization if editor is null. +% +{ editor empty$ + { organization empty$ + { key empty$ + { "no key, editor or organization in " cite$ * warning$ + cite$ #1 #3 substring$ } + 'key + if$ + } + { organization } + if$ + } + { editor format.lab.names } + if$ +} + +FUNCTION {author.editor.key.label} +{ author empty$ + { editor empty$ + { key empty$ + { "no key, author, or editor in " cite$ * warning$ + cite$ #1 #3 substring$ } + 'key + if$ + } + { editor format.lab.names } + if$ + } + { author format.lab.names } + if$ +} + +FUNCTION {calc.label.orig} +% +% Changed - GNP. See also author.organization.sort, editor.organization.sort +% Form label for BibTeX entry. The classification of which fields are used +% for which type of entry (book, inbook, etc.) are taken from alpha.bst. +% The change here from newapa is to also include organization as a +% citation label if author or editor is missing. +% +{ type$ "book" = + type$ "inbook" = + or + 'author.editor.key.label + { type$ "proceedings" = + 'editor.key.organization.label + { type$ "manual" = + 'author.key.organization.label + 'author.key.label + if$ + } + if$ + } + if$ + + author empty$ % generate the full label citation information. + { editor empty$ + { organization empty$ + { "no author, editor, or organization in " cite$ * warning$ + "??" } + { organization } + if$ + } + { editor my.full.label } + if$ + } + { author.key.label } + if$ + +% leave label on the stack, to be popped when required. + + "}{" * swap$ * +% year field.or.null purify$ #-1 #4 substring$ * +% +% save the year for sort processing afterwards (adding a, b, c, etc.) +% + year field.or.null purify$ #-1 #4 substring$ + 'label.year := +} + +FUNCTION {calc.label} +% +% Changed - GNP. See also author.organization.sort, editor.organization.sort +% Form label for BibTeX entry. The classification of which fields are used +% for which type of entry (book, inbook, etc.) are taken from alpha.bst. +% The change here from newapa is to also include organization as a +% citation label if author or editor is missing. +% +{ type$ "book" = + type$ "inbook" = + or + 'author.editor.key.label + { type$ "proceedings" = + 'editor.key.organization.label + { type$ "manual" = + 'author.key.organization.label + 'author.key.label + if$ + } + if$ + } + if$ + + author empty$ % generate the full label citation information. + { editor empty$ + { organization empty$ + { "no author, editor, or organization in " cite$ * warning$ + "??" } + { organization } + if$ + } + { editor my.full.label } + if$ + } + { author my.full.label } + if$ + +% leave label on the stack, to be popped when required. + + "}{" * swap$ * "}{" * title * "}{" * +% year field.or.null purify$ #-1 #4 substring$ * +% +% save the year for sort processing afterwards (adding a, b, c, etc.) +% + year field.or.null purify$ #-1 #4 substring$ + 'label.year := +} + +FUNCTION {output.bibitem} +{ newline$ + + "\bibitem[\protect\citeauthortitleyear{" write$ + calc.label write$ + sort.year write$ + "}]{" write$ + + cite$ write$ + "}" write$ + newline$ + "" + before.all 'output.state := +} + +FUNCTION {article} +{ output.bibitem + format.authors + "author" output.check + author format.key output % added + output.year.check % added + new.block + format.title + "title" output.check + new.block + crossref missing$ + { format.jour.vol output + } + { format.article.crossref output.nonnull + format.pages output + } + if$ + new.block + note output + fin.entry +} + +FUNCTION {book} +{ output.bibitem + author empty$ + { format.editors + "author and editor" output.check } + { format.authors + output.nonnull + crossref missing$ + { "author and editor" editor either.or.check } + 'skip$ + if$ + } + if$ + output.year.check % added + new.block + format.btitle + "title" output.check + crossref missing$ + { format.bvolume output + new.block + format.number.series output + new.sentence + address output + publisher "publisher" output.check.colon + } + { new.block + format.book.crossref output.nonnull + } + if$ + new.block + note output + fin.entry +} + +FUNCTION {booklet} +{ output.bibitem + format.authors output + author format.key output % added + output.year.check % added + new.block + format.title + "title" output.check + new.block + howpublished output + address output + new.block + note output + fin.entry +} + +FUNCTION {inbook} +{ output.bibitem + author empty$ + { format.editors + "author and editor" output.check + } + { format.authors output.nonnull + crossref missing$ + { "author and editor" editor either.or.check } + 'skip$ + if$ + } + if$ + output.year.check % added + new.block + format.btitle + "title" output.check + crossref missing$ + { format.bvolume output + format.chapter.pages + "chapter and pages" output.check + new.block + format.number.series output + new.sentence + address output + publisher + "publisher" output.check.colon + } + { format.chapter.pages "chapter and pages" output.check + new.block + format.book.crossref output.nonnull + } + if$ + new.block + note output + fin.entry +} + +FUNCTION {incollection} +{ output.bibitem + format.authors + "author" output.check + author format.key output % added + output.year.check % added + new.block + format.title + "title" output.check + new.block + crossref missing$ + { format.in.ed.booktitle + "booktitle" output.check + format.bvolume output + format.number.series output + format.chapter.pages output % gnp - was special.output.nonnull +% left out comma before page numbers + new.sentence + address output + publisher "publisher" output.check.colon + } + { format.incoll.inproc.crossref + output.nonnull + format.chapter.pages output + } + if$ + new.block + note output + fin.entry +} + +FUNCTION {inproceedings} +{ output.bibitem + format.authors + "author" output.check + author format.key output % added + output.year.check % added + new.block + format.title + "title" output.check + new.block + crossref missing$ + { format.in.ed.booktitle + "booktitle" output.check + format.bvolume output + format.number.series output + address output + format.pages output + new.sentence + organization output + publisher output.colon + } + { format.incoll.inproc.crossref output.nonnull + format.pages output + } + if$ + new.block + note output + fin.entry +} + +FUNCTION {conference} { inproceedings } + +FUNCTION {manual} +{ output.bibitem + author empty$ + { editor empty$ + { organization "organization" output.check + organization format.key output } % if all else fails, use key + { format.editors "author and editor" output.check } + if$ + } + { format.authors output.nonnull } + if$ + output.year.check % added + new.block + format.btitle + "title" output.check + organization address new.block.checkb +% Reversed the order of "address" and "organization", added the ":". + address output + organization "organization" output.check.colon +% address output +% ":" output +% organization output + new.block + note output + fin.entry +} + +FUNCTION {mastersthesis} +{ output.bibitem + format.authors + "author" output.check + author format.key output % added + output.year.check % added + new.block + format.title + "title" output.check + new.block + "Master's thesis" format.thesis.type output.nonnull + school "school" output.check + address output + new.block + note output + fin.entry +} + +FUNCTION {misc} +{ output.bibitem + format.authors output + author format.key output % added + output.year.check % added + title howpublished new.block.checkb + format.title output + new.block + howpublished output + new.block + note output + fin.entry +} + +FUNCTION {phdthesis} +{ output.bibitem + format.authors + "author" output.check + author format.key output % added + output.year.check % added + new.block + format.btitle + "title" output.check + new.block + "Ph.\ D. thesis" format.thesis.type output.nonnull + school "school" output.check + address output + new.block + note output + fin.entry +} + +FUNCTION {proceedings} +{ output.bibitem + editor empty$ + { organization output + organization format.key output } % gnp - changed from author format.key + { format.editors output.nonnull } + if$ +% author format.key output % gnp - removed (should be either +% editor or organization + output.year.check % added (newapa) + new.block + format.btitle + "title" output.check + format.bvolume output + format.number.series output + address output + new.sentence + organization output + publisher output.colon + new.block + note output + fin.entry +} + +FUNCTION {techreport} +{ output.bibitem + format.authors + "author" output.check + author format.key output % added + output.year.check % added + new.block + format.title + "title" output.check + new.block + format.tr.number output.nonnull + institution + "institution" output.check + address output + new.block + note output + fin.entry +} + +FUNCTION {unpublished} +{ output.bibitem + format.authors + "author" output.check + author format.key output % added + output.year.check % added + new.block + format.title + "title" output.check + new.block + note "note" output.check + fin.entry +} + +FUNCTION {default.type} { misc } + +MACRO {jan} {"January"} + +MACRO {feb} {"February"} + +MACRO {mar} {"March"} + +MACRO {apr} {"April"} + +MACRO {may} {"May"} + +MACRO {jun} {"June"} + +MACRO {jul} {"July"} + +MACRO {aug} {"August"} + +MACRO {sep} {"September"} + +MACRO {oct} {"October"} + +MACRO {nov} {"November"} + +MACRO {dec} {"December"} + +MACRO {acmcs} {"ACM Computing Surveys"} + +MACRO {acta} {"Acta Informatica"} + +MACRO {ai} {"Artificial Intelligence"} + +MACRO {cacm} {"Communications of the ACM"} + +MACRO {ibmjrd} {"IBM Journal of Research and Development"} + +MACRO {ibmsj} {"IBM Systems Journal"} + +MACRO {ieeese} {"IEEE Transactions on Software Engineering"} + +MACRO {ieeetc} {"IEEE Transactions on Computers"} + +MACRO {ieeetcad} + {"IEEE Transactions on Computer-Aided Design of Integrated Circuits"} + +MACRO {ipl} {"Information Processing Letters"} + +MACRO {jacm} {"Journal of the ACM"} + +MACRO {jcss} {"Journal of Computer and System Sciences"} + +MACRO {scp} {"Science of Computer Programming"} + +MACRO {sicomp} {"SIAM Journal on Computing"} + +MACRO {tocs} {"ACM Transactions on Computer Systems"} + +MACRO {tods} {"ACM Transactions on Database Systems"} + +MACRO {tog} {"ACM Transactions on Graphics"} + +MACRO {toms} {"ACM Transactions on Mathematical Software"} + +MACRO {toois} {"ACM Transactions on Office Information Systems"} + +MACRO {toplas} {"ACM Transactions on Programming Languages and Systems"} + +MACRO {tcs} {"Theoretical Computer Science"} + +READ + +FUNCTION {sortify} +{ purify$ + "l" change.case$ +} + +INTEGERS { len } + +FUNCTION {chop.word} +{ 's := + 'len := + s #1 len substring$ = + { s len #1 + global.max$ substring$ } + 's + if$ +} + + + +FUNCTION {sort.format.names} +{ 's := + #1 'nameptr := + "" + s num.names$ 'numnames := + numnames 'namesleft := + { namesleft #0 > } + { nameptr #2 = + { year field.or.null purify$ #-1 #4 substring$ * } + 'skip$ + if$ + nameptr #1 > + { " " * } + 'skip$ + if$ + s nameptr "{vv{ } }{ll{ }}{ f{ }}{ jj{ }}" format.name$ 't := + nameptr numnames = t "others" = and + { " et~al" * } + { t sortify * } + if$ + nameptr #1 + 'nameptr := + namesleft #1 - 'namesleft := + } + while$ +} + +FUNCTION {sort.format.title} +{ 't := + "A " #2 + "An " #3 + "The " #4 t chop.word + chop.word + chop.word + sortify + #1 global.max$ substring$ +} + +FUNCTION {author.sort} +{ author empty$ + { key empty$ + { "to sort, need author or key in " cite$ * warning$ + "" } + { key sortify } + if$ + } + { author sort.format.names } + if$ +} + +FUNCTION {editor.sort} +{ editor empty$ + { key empty$ + { "to sort, need editor or key in " cite$ * warning$ + "" + } + { key sortify } + if$ + } + { editor sort.format.names } + if$ +} + +FUNCTION {author.editor.sort} +{ author empty$ + { "missing author in " cite$ * warning$ + editor empty$ + { key empty$ + { "to sort, need author, editor, or key in " cite$ * warning$ + "" + } + { key sortify } + if$ + } + { editor sort.format.names } + if$ + } + { author sort.format.names } + if$ +} + +FUNCTION {author.organization.sort} +% +% added - GNP. Stack author or organization for sorting (from alpha.bst). +% Unlike alpha.bst, we need entire names, not abbreviations +% +{ author empty$ + { organization empty$ + { key empty$ + { "to sort, need author, organization, or key in " cite$ * warning$ + "" + } + { key sortify } + if$ + } + { organization sortify } + if$ + } + { author sort.format.names } + if$ +} + +FUNCTION {editor.organization.sort} +% +% added - GNP. Stack editor or organization for sorting (from alpha.bst). +% Unlike alpha.bst, we need entire names, not abbreviations +% +{ editor empty$ + { organization empty$ + { key empty$ + { "to sort, need editor, organization, or key in " cite$ * warning$ + "" + } + { key sortify } + if$ + } + { organization sortify } + if$ + } + { editor sort.format.names } + if$ +} + +FUNCTION {presort} +% +% Presort creates the bibentry's label via a call to calc.label, and then +% sorts the entries based on entry type. Chicago.bst adds support for +% including organizations as the sort key; the following is stolen from +% alpha.bst. +% +{ %calc.label sortify % recalculate bibitem label + %year field.or.null purify$ #-1 #4 substring$ * % add year + %duplicate$ warning$ + %" " + %* + type$ "book" = + type$ "inbook" = + or + 'author.editor.sort + { type$ "proceedings" = + 'editor.organization.sort + { type$ "manual" = + 'author.organization.sort + 'author.sort + if$ + } + if$ + } + if$ + #1 entry.max$ substring$ % added for newapa + 'sort.label := % added for newapa + sort.label % added for newapa + %* + " " + * + title field.or.null + sort.format.title + * + #1 entry.max$ substring$ + 'sort.key$ := +} + +ITERATE {presort} + +SORT % by label, year, author/editor, title + +STRINGS { last.label next.extra } + +INTEGERS { last.extra.num } + +FUNCTION {initialize.extra.label.stuff} +{ #0 int.to.chr$ 'last.label := + "" 'next.extra := + #0 'last.extra.num := +} + +FUNCTION {forward.pass} +% +% Pass through all entries, comparing current entry to last one. +% Need to concatenate year to the stack (done by calc.label) to determine +% if two entries are the same (see presort) +% +{ last.label + calc.label.orig year field.or.null purify$ #-1 #4 substring$ * % add year + #1 entry.max$ substring$ = % are they equal? + { last.extra.num #1 + 'last.extra.num := + last.extra.num int.to.chr$ 'extra.label := + } + { "a" chr.to.int$ 'last.extra.num := + "" 'extra.label := + calc.label.orig year field.or.null purify$ #-1 #4 substring$ * % add year + #1 entry.max$ substring$ 'last.label := % assign to last.label + } + if$ +} + +FUNCTION {reverse.pass} +{ next.extra "b" = + { "a" 'extra.label := } + 'skip$ + if$ + label.year extra.label * 'sort.year := + extra.label 'next.extra := +} + +EXECUTE {initialize.extra.label.stuff} + +ITERATE {forward.pass} + +REVERSE {reverse.pass} + +FUNCTION {bib.sort.order} +{ sort.label + " " + * + year field.or.null sortify + * + " " + * + title field.or.null + sort.format.title + * + #1 entry.max$ substring$ + 'sort.key$ := +} + +ITERATE {bib.sort.order} + +SORT % by sort.label, year, title --- giving final bib. order. + +FUNCTION {begin.bib} + +{ preamble$ empty$ + 'skip$ + { preamble$ write$ newline$ } + if$ + "\begin{thebibliography}{}" write$ newline$ +} + + +EXECUTE {begin.bib} + +EXECUTE {init.state.consts} + +ITERATE {call.type$} + +FUNCTION {end.bib} +{ newline$ + "\end{thebibliography}" write$ newline$ +} + +EXECUTE {end.bib} + diff --git a/doc/chicago.sty b/doc/chicago.sty new file mode 100644 index 0000000..ffe6508 --- /dev/null +++ b/doc/chicago.sty @@ -0,0 +1,318 @@ +% -*- LaTeX -*- +%%% ==================================================================== +%%% @LaTeX-style-file{ +%%% author = "Glenn Paulley", +%%% version = "4", +%%% date = "31 August 1992", +%%% time = "09:42:44 199", +%%% filename = "chicago.sty", +%%% address = "Data Structuring Group +%%% Department of Computer Science +%%% University of Waterloo +%%% Waterloo, Ontario, Canada +%%% N2L 3G1", +%%% telephone = "(519) 885-1211", +%%% FAX = "(519) 885-1208", +%%% checksum = "44674 264 1050 10394", +%%% email = "gnpaulle@bluebox.uwaterloo.ca", +%%% codetable = "ISO/ASCII", +%%% keywords = "", +%%% supported = "yes", +%%% abstract = "Contains the LaTeX style command definitions +%%% for the Chicago BibTeX styles chicago.bst and +%%% chicagoa.bst. For details, see below.", +%%% docstring = "The checksum field above contains a CRC-16 +%%% checksum as the first value, followed by the +%%% equivalent of the standard UNIX wc (word +%%% count) utility output of lines, words, and +%%% characters. This is produced by Robert +%%% Solovay's checksum utility.", +%%% } +%%% ==================================================================== +% +% chicago.sty: Style file for use with bibtex style chicago.bst, for +% bibliographies formatted according to the 13th Edition of the Chicago +% Manual of Style. +% +% 'newapa.bst' was made from 'plain.bst', 'named.bst', and 'apalike.bst', +% with lots of tweaking to make it look like APA style, along with tips +% from Young Ryu and Brian Reiser's modifications of 'apalike.bst'. +% newapa.sty formed the basis of this style, chicago.sty. Author-date +% references in newapa.bst formed the basis for chicago.bst. Chicagoa.bst +% supports annotations. +% +% Version 4 (August, 1992): +% - fixed chicago.bst and chicagoa.bst to handle long author lists in +% sorting +% - fixed chicago.bst and chicagoa.bst so that missing page numbers in +% ``article'' entries are handled correctly +% - modified chicago.sty to format entries with 2nd and subsequent lines +% indented. +% +% Citation format: (author-last-name year) +% (author-last-name and author-last-name year) +% (author-last-name et al. year) +% (author-last-name) +% author-last-name +% author-last-name (year) +% (author-last-name and author-last-name) +% (author-last-name et al.) +% (year) or (year,year) +% year or year,year +% +% Reference list ordering: alphabetical by author or whatever passes +% for author in the absence of one. +% +% This BibTeX style has support for abbreviated author lists and for +% year-only citations. This is done by having the citations +% actually look like +% +% \citeauthoryear{full-author-info}{abbrev-author-info}{year} +% +% The LaTeX style has to have the following (or similar) +% +% \let\@internalcite\cite +% \def\fullcite{\def\citeauthoryear##1##2##3{##1, ##3}\@internalcite} +% \def\fullciteA{\def\citeauthoryear##1##2##3{##1}\@internalcite} +% \def\shortcite{\def\citeauthoryear##1##2##3{##2, ##3}\@internalcite} +% \def\shortciteA{\def\citeauthoryear##1##2##3{##2}\@internalcite} +% \def\citeyear{\def\citeauthoryear##1##2##3{##3}\@internalcite} +% +% ------------------------------------------------------------------------- +% This file implements citations for the ``chicago'' bibliography style. +% Place it in a file called chicago.sty in the TeX search path. +%(Placing it in the same directory as the LaTeX document should also work.) +% +% This file is a modification of the ``newapa'' LaTeX style, +% originally adapted by Steven Spencer from the ``apalike'' LaTeX style. +% It was originally modified by Stephen N. Spencer, with further +% modifications by Young U. Ryu. +% +% The ``chicago'' BibTeX bibliography style creates citations with labels: +% \citeauthoryear{author-info}{abbrev. author-info}{year} +% +% These labels are processed by the following LaTeX commands: +% +% \cite{key} +% which produces citations with full author list and year. +% eg. (Brown 1978; Jarke, Turner, Stohl, et al. 1985) +% \citeNP{key} +% which produces citations with full author list and year, but without +% enclosing parentheses: +% eg. Brown 1978; Jarke, Turner and Stohl 1985 +% \citeA{key} +% which produces citations with only the full author list. +% eg. (Brown; Jarke, Turner and Stohl) +% \citeANP{key} +% which produces citations with only the full author list, without +% parentheses eg. Brown; Jarke, Turner and Stohl +% \citeN{key} +% which produces citations with the full author list and year, but +% can be used as nouns in a sentence; no parentheses appear around +% the author names, but only around the year. +% eg. Shneiderman (1978) states that...... +% \citeN should only be used for a single citation. +% \shortcite{key} +% which produces citations with abbreviated author list and year. +% \shortciteNP{key} +% which produces citations with abbreviated author list and year. +% \shortciteA{key} +% which produces only the abbreviated author list. +% \shortciteANP{key} +% which produces only the abbreviated author list. +% \shortciteN{key} +% which produces the abbreviated author list and year, with only the +% year in parentheses. Use with only one citation. +% \citeyear{key} +% which produces the year information only, within parentheses. +% \citeyearNP{key} +% which produces the year information only. +% +% Abbreviated author lists use the ``et al.'' construct. +% +% `NP' means `no parentheses'. +% +% This LaTeX style file must be used with the ``chicago'' or ``chicagoa'' +% (annotated chicago style) BibTeX styles. +% +\typeout{Using Chicago Manual of Style bibliography: 31 August 1992} +% +% ------------------------------------------------------------------------- +% +% Citation macros. +% +\def\chicagoand/{ and } +\def\chicagoetal/{ et~al.} +% +\let\@internalcite\cite +% +\def\cite{\def\@citeseppen{-1000}% + \def\@cite##1##2{(##1\if@tempswa , ##2\fi)}% + \def\citeauthortitleyear##1##2##3##4{##1\ ##4}\@internalcite} +\def\citeNP{\def\@citeseppen{-1000}% + \def\@cite##1##2{##1\if@tempswa , ##2\fi}% + \def\citeauthortitleyear##1##2##3##4{##1\ ##4}\@internalcite} +\def\citetitleN{\def\@citeseppen{-1000}% + \def\@cite##1##2{##1\if@tempswa , ##2)\else{)}\fi}% + \def\citeauthortitleyear##1##2##3##4{##3\ (##1; ##4}\@citedata} +\def\citeN{\def\@citeseppen{-1000}% + \def\@cite##1##2{##1\if@tempswa , ##2)\else{)}\fi}% + \def\citeauthortitleyear##1##2##3##4{##1\ (##4}\@citedata} +\def\citeA{\def\@citeseppen{-1000}% + \def\@cite##1##2{(##1\if@tempswa , ##2\fi)}% + \def\citeauthortitleyear##1##2##3##4{##1}\@internalcite} +\def\citeANP{\def\@citeseppen{-1000}% + \def\@cite##1##2{##1\if@tempswa , ##2\fi}% + \def\citeauthortitleyear##1##2##3##4{##1}\@internalcite} +% +\def\shortcite{\def\@citeseppen{-1000}% + \def\@cite##1##2{(##1\if@tempswa , ##2\fi)}% + \def\citeauthortitleyear##1##2##3##4{##2\ ##4}\@internalcite} +\def\shortciteNP{\def\@citeseppen{-1000}% + \def\@cite##1##2{##1\if@tempswa , ##2\fi}% + \def\citeauthortitleyear##1##2##3##4{##2\ ##4}\@internalcite} +\def\shortciteN{\def\@citeseppen{-1000}% + \def\@cite##1##2{##1\if@tempswa , ##2)\else{)}\fi}% + \def\citeauthortitleyear##1##2##3##4{##2\ (##4}\@citedata} +\def\shortciteA{\def\@citeseppen{-1000}% + \def\@cite##1##2{(##1\if@tempswa , ##2\fi)}% + \def\citeauthortitleyear##1##2##3##4{##2}\@internalcite} +\def\shortciteANP{\def\@citeseppen{-1000}% + \def\@cite##1##2{##1\if@tempswa , ##2\fi}% + \def\citeauthortitleyear##1##2##3##4{##2}\@internalcite} +% +\def\citeyear{\def\@citeseppen{-1000}% + \def\@cite##1##2{(##1\if@tempswa , ##2\fi)}% + \def\citeauthortitleyear##1##2##3##4{##4}\@citedata} +\def\citeyearNP{\def\@citeseppen{-1000}% + \def\@cite##1##2{##1\if@tempswa , ##2\fi}% + \def\citeauthortitleyear##1##2##3##4{##4}\@citedata} + +% +% \@citedata and \@citedatax: +% +% Place commas in-between citations in the same \citeyear, \citeyearNP, +% \citeN, or \shortciteN command. +% Use something like \citeN{ref1,ref2,ref3} and \citeN{ref4} for a list. +% +\def\@citedata{% + \@ifnextchar [{\@tempswatrue\@citedatax}% + {\@tempswafalse\@citedatax[]}% +} + +\def\@citedatax[#1]#2{% +\if@filesw\immediate\write\@auxout{\string\citation{#2}}\fi% + \def\@citea{}\@cite{\@for\@citeb:=#2\do% + {\@citea\def\@citea{), }\@ifundefined% by Young + {b@\@citeb}{{\bf ?}% + \@warning{Citation `\@citeb' on page \thepage \space undefined}}% +{\csname b@\@citeb\endcsname}}}{#1}}% + +\@ifpackageloaded{hyperref}{% + \let\BRorg@citedatax\@citedatax + \def\@citedatax[#1]#2{% + \BRorg@citedatax[#1]{#2}% + \Hy@backout{#2}% + }% +}{} +\@ifpackageloaded{hyperref}{% +\def\hyperemph#1{{\em\hyperpage{#1}}}% +\def\bold#1{{\bf\hyperpage{#1}}}% +}{% +\def\hyperemph#1{{\em #1}}% +\def\bold#1{{\bf #1}}% +} + +\def\BR@@lbibitem[#1]#2#3\par{% + \BRorg@bibitem[#1]{#2}#3\hfill\penalty100\hbox{} + \newblock + \backref\hfill[{\csname br@#2\endcsname}% + ]\parskip=-10pt\penalty-10000\hbox{}\nobreak\par +}% +\def\BR@@bibitem#1#2\par{% + \BRorg@bibitem{#1}#2 + \newblock + \backref\penalty-100\hbox{}\nobreak\hfill[\hbox{\csname br@#2\endcsname}% + ]\par +} +\def\thepageorcolor{\thepage} +\def\Hy@backout#1{% + \@bsphack + \ifx\@empty\@currentlabel + \protected@write\@auxout{}{% + \string\@writefile{brf}{% + \string\backcite{#1}{{\thepageorcolor}{(document)}{Doc-Start}}% + }% + }% + \else + \protected@write\@auxout{}{% + \string\@writefile{brf}{% + \string\backcite{#1}{{\thepageorcolor}{\@currentlabel}{\@currentHref}}% + }% + }% + \fi + \@esphack +} + +% don't box citations, separate with ; and a space +% also, make the penalty between citations negative: a good place to break. +% +\def\@citex[#1]#2{% +\if@filesw\immediate\write\@auxout{\string\citation{#2}}\fi% + \def\@citea{}\@cite{\@for\@citeb:=#2\do% + {\@citea\def\@citea{; }\@ifundefined% by Young + {b@\@citeb}{{\bf ?}% + \@warning{Citation `\@citeb' on page \thepage \space undefined}}% +{\csname b@\@citeb\endcsname}}}{#1}}% + +% (from apalike.sty) +% No labels in the bibliography. +% +\def\@biblabel#1{} + +% (from apalike.sty) +% Set length of hanging indentation for bibliography entries. +% +\newlength{\bibhang} +\setlength{\bibhang}{2em} + +% Indent second and subsequent lines of bibliographic entries. Stolen +% from openbib.sty: \newblock is set to {}. + +\newdimen\bibindent +\bibindent=1.5em +\@ifundefined{refname}% + {\@ifundefined{chapter}% + {\newcommand{\refname}{References}}% + {\newcommand{\refname}{Bibliography}}% + }% + {}% +\@ifundefined{chapter}% + {\def\thebibliography#1{\section*{\refname\@mkboth + {\uppercase{\refname}}{\uppercase{\refname}}}\list + {[\arabic{enumi}]}{\settowidth\labelwidth{[#1]} + \leftmargin\labelwidth + \advance\leftmargin\labelsep + \advance\leftmargin\bibindent + \itemindent -\bibindent + \listparindent \itemindent + \parsep \z@ + \usecounter{enumi}} + \def\newblock{} + \sloppy + \sfcode`\.=1000\relax}} + {\def\thebibliography#1{\chapter*{\refname\@mkboth + {\refname}{\refname}} + \addcontentsline{toc}{chapter}{References} + \list + {[\arabic{enumi}]}{\settowidth\labelwidth{[#1]} + \leftmargin\labelwidth + \advance\leftmargin\labelsep + \advance\leftmargin\bibindent + \itemindent -\bibindent + \listparindent \itemindent + \parsep \z@ + \usecounter{enumi}} + \def\newblock{} + \sloppy + \sfcode`\.=1000\relax}} diff --git a/doc/mydefs.sty b/doc/mydefs.sty new file mode 100644 index 0000000..d5dbf72 --- /dev/null +++ b/doc/mydefs.sty @@ -0,0 +1,198 @@ +\usepackage{amsmath,amsfonts,amssymb,makeidx} +\usepackage{glosstex} + +\glxitemorderdefault{acr}{l} + +\def\indac#1{% +\ac{#1}% +\expandafter\ifx\csname GLX@term@@#1\endcsname\relax% +\else% + \index{\csname GLX@term@@#1\endcsname\space% + (\csname GLX@term@#1\endcsname)}% +\fi} + +\def\andindex{% +\@ifnextchar[{\@ndindex}% +{\@ndind@x}} +\def\@ndindex[#1]#2{% +{#1#2}\index{#2@{#1#2}}} +\def\@ndind@x#1{% +{#1\index{#1}}} +\def\defindex#1{% +{{\em #1}\index{#1|bold}}} + +\let\ai=\andindex + +\newcount\prefcount +\newcount\rpage + +\def\pref#1{% +\global\advance\prefcount by 1% +\edef\foo{pref\the\prefcount}% +\label\foo% +\rpage=\simple@pageref\foo% +\advance\rpage by -\simple@pageref{#1}% +\ref{#1}% +\ifnum\rpage=0% +\else\ifnum\rpage=1% +\ on the previous page% +\else\ifnum\rpage=-1% +%\ on the next page% +\else% +\ on page~\pageref{#1}% +\fi\fi\fi% +} + +\def\npref#1{% +\global\advance\prefcount by 1% +\edef\foo{pref\the\prefcount}% +\label\foo% +\rpage=\simple@pageref\foo% +\advance\rpage by -\simple@pageref{#1}% +\ref{#1}% +\ifnum\rpage=0% +\else\ifnum\rpage=1% +\ on the previous page% +\else\ifnum\rpage=-1% +%\ on the next page% +\else% +\ op bladzijde~\pageref{#1}% +\fi\fi\fi% +} + +\def\sindex#1#2{\index{#2!#1|see{#1 #2}}} +\def\ssindex#1#2{\index{#2!#1|see{#1#2}}} +\def\tindex#1#2{\index{#2@{\tt #2}!{\tt #1::}|see{{\tt #1\discretionary{}{}{}::\discretionary{}{}{}#2}}}} + +\newtheorem{theorem}{Theorem} +\newtheorem{definition}[theorem]{Definition} +\newtheorem{proposition}[theorem]{Proposition} +\newtheorem{lemma}[theorem]{Lemma} +\newtheorem{corollary}[theorem]{Corollary} +\newcounter{ex} +\newenvironment{example} + {\refstepcounter{ex} + \begin{quote}\small\noindent{\bf Example \theex}} + {\end{quote}} +\numberwithin{theorem}{section} + +\def\NN{\mathbb{N}} +\def\ZZ{\mathbb{Z}} +\def\QQ{\mathbb{Q}} +\def\RR{\mathbb{R}} +\def\CC{\mathbb{C}} +\def\lb{\left\{} +\def\rb{\right\}} +\def\nc{\nomenclature} + +\def\convhull{\mathop{\rm conv}\nolimits} +\def\affhull{\mathop{\rm aff}\nolimits} +\def\linhull{\mathop{\rm lin}\nolimits} +\def\poshull{\mathop{\rm pos}\nolimits} +\def\lexmin{\mathop{\rm lexmin}} +\def\lexmax{\mathop{\rm lexmax}} +\def\dcone{\mathop{\rm dcone}\nolimits} +\def\rank{\mathop{\rm rank}\nolimits} +\def\Ker{\mathop{\rm Ker}\nolimits} +\def\Im{\mathop{\rm Im}\nolimits} +\def\argmax{\mathop{\rm argmax}} + +\def\bold#1{{\bf #1}} + +\providecommand{\abs}[1]{\left|#1\right|} +\providecommand{\norm}[1]{\left\lVert#1\right\rVert} +\providecommand{\floor}[1]{\left\lfloor#1\right\rfloor} +\providecommand{\ceil}[1]{\left\lceil#1\right\rceil} +\providecommand{\fractional}[1]{\left\{#1\right\}} +\providecommand{\Iverson}[1]{\left[#1\right]} +\DeclareMathOperator{\cone}{cone} + +\def\sm#1{ + \left[ + \begin{matrix} + #1 + \end{matrix} + \right] +} + +\def\VR{{\cal V}} +\def\sp#1#2{\langle\vec #1,\vec #2\rangle} +\def\sps#1#2{\langle #1, #2\rangle} +\def\T{{\scriptscriptstyle T}} +\def\f#1#2{f(#1; \vec #2)} +\def\ff#1#2{f(#1; #2)} + +\def\indf#1{\left[#1\right]} + +\def\LattE/{\ai[\tt]{LattE}} +\def\PolyLib/{\ai[\tt]{PolyLib}} +\def\Omegalib/{\ai[\tt]{Omega}} +\def\barvinok/{\ai[\tt]{barvinok}} +\def\psp/{piecewise step-poly\-no\-mi\-al} +\def\rgf/{rational generating function} +\def\vm#1{\underline{\vec #1}} + +\newcommand{\R}{\ensuremath{{\mathcal R}}} +\newcommand{\reuse}[2]{\ensuremath{\textrm{\sf reuse}_{#1}^{#2}}} +\newcommand{\ADS}[2]{\ensuremath{\textrm{\sf ADS}_{#1}^{#2}}} +\newcommand{\BRD}[2]{\ensuremath{\textrm{\sf BRD}_{#1}^{#2}}} +\let\from\leftarrow + +\def\vec#1{\mathchoice{\mbox{\boldmath$\displaystyle\bf#1$}} +{\mbox{\boldmath$\textstyle\bf#1$}} +{\mbox{\boldmath$\scriptstyle\bf#1$}} +{\mbox{\boldmath$\scriptscriptstyle\bf#1$}}} + +\def\DP{\mbox{\sl DP\/}} +\def\DD{\mbox{\sl DD\/}} +\def\DF{\mbox{\sl DF\/}} + +\def\Rd{R_{\rm d}} +\def\rd{r_{\rm d}} + +\@ifpackageloaded{hyperref}{% +\def\eqdeclaration#1{, see Equation\nobreakspace(#1)}% +\def\pagedeclaration#1{, page\nobreakspace\hyperpage{#1}}% +\def\addcontentsline#1#2#3{% toc extension, type, tag + \begingroup + \let\label\@gobble + \let\textlatin\@firstofone + \ifx\@currentHref\@empty + \Hy@Warning{% + No destination for bookmark of \string\addcontentsline,% + \MessageBreak destination is added% + }% + \phantomsection + \fi + \expandafter\ifx\csname toclevel@#2\endcsname\relax + \begingroup + \def\Hy@tempa{#1}% + \ifx\Hy@tempa\Hy@bookmarkstype + \Hy@WarningNoLine{bookmark level for unknown #2 defaults to 0}% + \else + \Hy@Info{bookmark level for unknown #2 defaults to 0}% + \fi + \endgroup + \expandafter\gdef\csname toclevel@#2\endcsname{0}% + \fi + \edef\Hy@toclevel{\csname toclevel@#2\endcsname}% + \Hy@writebookmark{\csname the#2\endcsname}% + {#3}% + {\@currentHref}% + {\Hy@toclevel}% + {#1}% + \ifHy@verbose + \typeout{pdftex: bookmark at \the\inputlineno: + {\csname the#2\endcsname} + {#3} + {\@currentHref}% + {\Hy@toclevel}% + {#1}% + }% + \fi + \addtocontents{#1}{% + \protect\contentsline{#2}{#3}{\protect\hyperpage{\thepage}}{\@currentHref}% + }% + \endgroup +} +}{} -- 2.11.4.GIT