More Precise Yet Efficient Type Inference for Logic Programs
Claudio Vaucheret
Francisco Bueno
Type analyses of logic programs which aim at inferring the types of the program being analyzed are presented in a unified abstract interpretation-based framework. This covers most classical abstract interpretation-based type analyzers for logic programs, built on either top-down or bottom-up interpretation of the program. In this setting, we discuss the widening operator, arguably a crucial one. We present a new widening which is more precise than those previously proposed. Practical results with our analysis domain are also presented, showing that it also allows for efficient analysis.
p08.tex
\NeedsTeXFormat{LaTeX2e}
\documentclass[runningheads]{llncs}

\usepackage{latexsym}
\usepackage{pstricks,pst-node,pst-text,pst-3d}
\renewcommand{\floatpagefraction}{0.90}
%\newcounter{08example}
\newenvironment{08example}{\begin{example}}{\end{example}}
\newcommand{\reach}{\stackrel{\tiny reach}{\longrightarrow}}
\newcommand{\pow}[1]{2^{#1}}
\newcommand{\ssubseteq}{\widehat{\sqsubseteq}}
\newcommand{\scup}{\widehat{\sqcup}}
\newcommand{\scap}{\widehat{\sqcap}}
\newcommand{\lcons}{\mbox{\tt '.'}}
\newcommand{\abigcup}[1]{\stackrel{#1}{\bigcup}}

\begin{document}
\setcounter{page}{63}
\title{More Precise Yet Efficient Type Inference for Logic Programs}
\titlerunning{More Precise Yet Efficient Type Inference for Logic Programs}
\author{Claudio Vaucheret \and Francisco Bueno}
\authorrunning{C. Vaucheret, F. Bueno}
\institute{Technical University of Madrid (UPM), Spain\\
           \email{\{claudio,bueno\}@fi.upm.es}}

\maketitle

\addtocounter{footnote}{1}
\footnotetext{In Alexandre Tessier (Ed), proceedings of the 12th International Workshop on Logic Programming Environments (WLPE 2002), July 2002, Copenhagen, Denmark.\\Proceedings of WLPE 2002: \texttt{http://xxx.lanl.gov/html/cs/0207052} (CoRR)}

\begin{abstract}
Type analyses of logic programs which aim at inferring the types of
the program being analyzed are presented in a unified abstract
interpretation-based framework. This covers most classical abstract
interpretation-based type analyzers for logic programs, built on
either top-down or bottom-up 
interpretation of the program. In this setting, we discuss the
widening operator, arguably a crucial one. We present a new widening
which is more precise than those previously proposed. Practical
results with our analysis domain are also presented, showing that it
also allows for efficient analysis.
\end{abstract}

\section{Introduction}

In type analyses, the widening operation has much influence in the
results. If the widening is too aggressive in making approximations
then the analysis results may be too imprecise. On the other hand,
if it is not sufficiently aggressive then the analysis may become
too inefficient. 

Widening operators are aimed at identifying the recursive structure
of the types being inferred. All widenings already proposed
in the literature are based on locating type nodes with the same
functors, which are possible sources of recursion. However, they
disregard whether such nodes come in fact from a recursive structure
in the program or not. This may originate an unnecessary loss of
precision, since the widening result may then impose a recursive
structure on the resulting type in argument positions where the
concrete program is in fact not recursive. We propose a widening
operator to try to remedy this problem. 

We present our widening operator for regular type inference in an
analysis framework based on abstract interpretation of the program.
In order for the paper to be self contained, we first revisit
regular types (Section~\ref{sec:regtypes}) and, in particular,
deterministic ones. We focus on deterministic types for ease of
presentation; however, there is nothing in our widening which prevents
it to be applicable also to non-deterministic types. The abstract
interpretation framework is set up in
Section~\ref{sec:domain}. Section~\ref{sec:widenings} 
reviews previous widenings in the literature, and
Section~\ref{sec:grammarwithnames} presents ours. In
Section~\ref{sec:results} experimental results are presented, and
Section~\ref{sec:conclusions} concludes and discusses future work. 

\section{Regular Types}
\label{sec:regtypes}

A {\em regular type}~\cite{Dart-Zobel} is a type representing a class
of terms that can be described by a regular term grammar.
A \emph{regular term grammar}, or grammar for short, describes a set of
finite terms constructed from a finite alphabet ${\cal F}$ of
\emph{ranked function symbols} or \emph{functors}.
%
A grammar $G = (S,{\cal T},{\cal F},{\cal R})$ consists of a
set of non-terminal symbols ${\cal T}$, one distinguished
symbol $S\in{\cal T}$, and a finite set ${\cal R}$ of
productions $T\longrightarrow rhs$, where $T \in {\cal T}$ is a
non-terminal and the right hand side $rhs$ is either a non-terminal or
a term $f(T_1,\ldots,T_n)$ constructed from an $n$-ary function symbol
$f \in {\cal F}$ and $n$ non-terminals. 

The non-terminals ${\cal T}$ are {\em types} describing (ground) terms
built from the functors in ${\cal F}$. The concretization $\gamma(T)$
of a non-terminal $T$ is the set of terms derivable from its productions,
that is, 
\begin{eqnarray*}
\gamma(T) & = & \bigcup_{(T \longrightarrow rhs) \in {\cal R}}
      \gamma(rhs) \\
\gamma(f(T_1,\ldots,T_n)) & = & \{ f(t_1,\ldots,t_n) ~|~
                                     t_i \in \gamma(T_i) \}
\end{eqnarray*}

The types of interest are each defined by one grammar: each $T_i$ is
defined by a grammar $(T_i,{\cal T}_i,{\cal F},{\cal R}_i)$, so that for
any two types of interest $T_1$ and $T_2$ on ${\cal F}$, 
${\cal T}_1\cap{\cal T}_2=\emptyset$. Sometimes, we will be interested
in types defined by non-terminals of a grammar 
$(T,{\cal T},{\cal F},{\cal R})$ other than the distinguished
non-terminal $T$. This is formalized by defining a type $T_i\in{\cal T}$
as the grammar  
%
\begin{equation}\label{eq:restrict}
(T_i,\{ T\in {\cal T} ~|~ T_i \reach^*_{\cal R} T \},
               {\cal F},\{ (T \longrightarrow rhs)\in {\cal R}
                        ~|~ T_i \reach^*_{\cal R} T \})
\end{equation}
where all the non-terminals are renamed apart, $\reach^*_{\cal R}$ is
the reflexive and transitive closure of $\reach_{\cal R}$ and
 $T_i \reach_{\cal R} T_j
   \mbox{ iff } T_i \longrightarrow_{\cal R} T_j 
   \mbox{ or }  T_i \longrightarrow_{\cal R} f(\ldots,T_j,\ldots)$.


A grammar is in \emph{normal form} if none of the right hand sides are
non-terminals.  A particular class of grammars are deterministic ones. 
A grammar is \emph{deterministic} if it is in normal form
and for each non-terminal $T$ the function symbols are all distinct in
the right hand sides of the productions for $T$.  

Deterministic grammars are less expressive than non-deterministic ones.
Deterministic grammars can only express sets of terms which are
\emph{tuple-distributive}; informally speaking, which are ``closed
under exchange of arguments''. I.e., if the set contains two terms of
the same functor, then it also contains terms with the same principal
functor obtained by exchanging subterms of the previous two terms in
the same argument positions. Basically, no dependencies between
arguments of a term can be expressed with deterministic grammars.

\begin{08example} 
Consider the type $T$ denoting the set $\{f(a,b),f(c,d)\}$, which is
non-deterministic,
$$\begin{array}{lllllllllll}
  T & \longrightarrow & f(A,B) && A & \longrightarrow & a && C & \longrightarrow & c \\ 
  T & \longrightarrow & f(C,D) && B & \longrightarrow & b && D & \longrightarrow & d    
  \end{array}$$
A deterministic type $T'$ with a concretization which included
$\gamma(T)$ would also have to include $\{f(c,b),f(a,d)\}$, that is,
$$\begin{array}{lllllllllll}
  T' & \longrightarrow & f(AC,BD) && AC & \longrightarrow & a && BD & \longrightarrow & b \\
     &                 &          && AC & \longrightarrow & c && BD & \longrightarrow & d
  \end{array}$$
To facilitate the presentation non-terminals with a single production
will often be ``inlined'' and multiple right hand sides combined so
that $T$ above will be written 
$T \longrightarrow f(a,b) \ | \ f(c,d)$ and $T'$ as
$$\begin{array}{lllllllllll}
  T' & \longrightarrow & f(AC,BD) && AC & \longrightarrow & a \  | \ c &&
  BD & \longrightarrow & b \  | \ d
  \end{array}$$
\vspace{-2\baselineskip}
\end{08example}

To be able to describe terms containing numbers and variables we
introduce two distinguished symbols \textbf{num} and \textbf{any},
plus an additional $\bot$. The concretization of \textbf{num} is the
set of all numbers, the concretization of \textbf{any} is the set
of all terms (including variables), and the concretization of $\bot$ is
the empty set of terms. These symbols are non-terminals but they are
considered terminals to the effect of regarding a grammar as
deterministic. 

Let $\mathcal{G}$ be the set of all grammars, if $T_1$, $T_2$ belong to
$\mathcal{G}$, the relation $T_1 \equiv T_2 \Leftrightarrow \gamma(T_1) =
\gamma(T_2)$ is an equivalence relation. The quotient set
$\mathcal{G}/\equiv$ is a complete lattice with top element \textbf{any}
and bottom element $\bot$ based on the relation of {\em containment}, or
type {\em inclusion}: for every 
$\overline{T_1},\overline{T_2} \in \mathcal{G}/\equiv$,
$\overline{T_1} \sqsubseteq \overline{T_2}
\Leftrightarrow \gamma(T_1)\subseteq\gamma(T_2)$.
% where
% and $T_i$ is the representative of the equivalence class $\overline{T_i}$
%
% Non-terminals, and therefore,
% grammars are ordered by the relation of {\em containment}, or type {\em
%   inclusion}, $(T_1 \sqsubseteq T_2) \Leftrightarrow
% \gamma(T_1)\subseteq\gamma(T_2)$.  Based on this, the set of all grammars
% $\mathcal{G}$ is a complete lattice with top element \textbf{any} and
% bottom element $\bot$. 
%
We will denote $\overline{T_i}$ simply by $T_i$.

The least upper bound is given by type {\em union},
$({T_1} \sqcup {T_2})$, and the greatest lower bound by 
type {\em intersection}, 
$({T_1} \sqcap {T_2})$~\cite{Dart-Zobel}. It can be shown that
intersection describes term unification:
\[ t_1^*\subseteq\gamma(T_1)\wedge t_2^*\subseteq\gamma(T_2)\wedge 
   t_1\theta=t_2\theta \Rightarrow 
   (t_1\theta)^*\subseteq\gamma(T_1 \sqcap T_2)
\]
where $t^*$ denotes the set of ground terms which are instances of the
term $t$.

\section{Abstract Domain for Type Inference}
\label{sec:domain}

In an abstract interpretation-based type analysis, a type is
used as an abstract description of a set of terms. Given variables of
interest $\{x_1,\ldots,x_n\}$, any substitution
$\theta = \{x_1 \leftarrow t_1,\ldots,x_n \leftarrow t_n\}$
can be approximated by an {\em abstract substitution} 
$\{x_1 \leftarrow T_{x_1},\ldots,x_n \leftarrow T_{x_n}\}$
where $t_i \in \gamma(T_{x_i})$ and each type $T_{x_i} \in \mathcal{G/\equiv}$.
%
We will write abstract substitutions as tuples
$\langle T_1,\ldots,T_n \rangle$, and sometimes also abbreviate a
tuple simply as $T^n$.

Concretization is lifted up to abstract substitutions
straightforwardly, 
$$\begin{array}{rcl}
\gamma(\langle T_1,\ldots,T_n \rangle) & = & 
\{~\{x_1 \leftarrow t_1,\ldots,x_n \leftarrow t_n\}~|~t_i \in \gamma(T_i)~\}
\end{array}$$
as well as the equivalence relation $\equiv$. Additionally,
 we consider a distinguished abstract
substitution {\boldmath$\bot$} as a representative of any 
$\langle T_1,\ldots,T_n\rangle$ such that there is $T_i=\bot$.
Of course, $\gamma(${\boldmath$\bot$}$)=\emptyset$.

An ordering on the domain is obtained as the natural element-wise
extension of the ordering on types:
$$\begin{array}{rcl}
 \begin{array}[b]{rcl}
    \mbox{\boldmath $\bot$} & \sqsubseteq & T^n \\
    \langle T_1,\ldots,T_n \rangle & \not \sqsubseteq & \mbox{\boldmath $\bot$} \\
    \langle T_1,\ldots,T_n \rangle & \sqsubseteq & \langle T'_1,\ldots,T'_n \rangle \\
 \end{array} & \Longleftrightarrow & \forall_{1 \leq i \leq n}T_i
    \sqsubseteq T'_i
%%  \\
%% T^n  \equiv  T'^n & \Longleftrightarrow & T^n \sqsubseteq T'^n \wedge
%% T'^n \sqsubseteq T^n
\end{array}$$
The domain is a lattice with bottom element {\boldmath $\bot$} and top element
$\langle T_1,\ldots,T_n \rangle$ such that $T_1=\ldots=T_n=\textbf{any}$.
%
The greatest lower bound and least upper bound domain operations are
lifted also element-wise, as follows,
$$\begin{array}{rcl}
\mbox{\boldmath $\bot$} \sqcup T^n  =  T^n \sqcup \mbox{\boldmath $\bot$} & = & T^n \\
\langle T_1,\ldots,T_n \rangle \sqcup \langle T'_1,\ldots,T'_n \rangle
& = & \langle T_1 \sqcup T'_1 ,\ldots,T_n \sqcup T'_n \rangle \\
\mbox{\boldmath $\bot$} ~ \sqcap ~ T^n  =  T^n ~ \sqcap ~ \mbox{\boldmath $\bot$} 
& = & \mbox{\boldmath $\bot$} \\
\langle T_1,\ldots,T_n \rangle ~ \sqcap ~ \langle T'_1,\ldots,T'_n \rangle
& = & \langle T_1 \sqcap T'_1 ,\ldots,T_n \sqcap T'_n \rangle
%% \bot \bigtriangledown  \langle T'_1,\ldots,T'_n \rangle 
%% & = & \langle \bot \bigtriangledown T'_1,\ldots,\bot \bigtriangledown T'_n \rangle
%% \\
%% \langle T_1,\ldots,T_n \rangle \bigtriangledown \langle T'_1,\ldots,T'_n \rangle
%% & = & \langle T_1 \bigtriangledown T'_1 ,\ldots,T_n \bigtriangledown T'_n \rangle
\end{array}$$

Using the adjoint $\alpha$ of $\gamma$ as abstraction function, it can
be shown that $(\pow{\Theta},\alpha,\Omega,\gamma)$ is a Galois
insertion, where $\Theta$ is the domain of concrete % substitutions 
and $\Omega$ that of abstract substitutions. 
%
The following abstract unification operator can be shown to approximate the
concrete one. Let $x=t$ be a concrete unification equation, with $x$ a
variable,$t$ any term, and $T^n$ the current abstract substitution, and
let $y_j$, $j=1,\ldots,m$ be the variables of $t$,
the new abstract substitution is:
\begin{equation}\label{eq:amgu}
amgu(T^n,x=t)=
T^n[T_x/T'_x,T_{y_1}/T'_{y_1},\ldots,T_{y_m}/T'_{y_m}]
\end{equation}
with each $T$ replaced by $T'$ in the
tuple, $T'_x = T_x\sqcap t\mu$, 
$\mu=\{y_1\leftarrow T_{y_1},\ldots,y_m\leftarrow T_{y_m}\}$, and 
$solve(t,T'_x) = \{ y_1=T'_{y_1},\ldots,y_m=T'_{y_m} \}$, a set of
equations that define the 
types of the variables of a term $t\in\gamma(T'_x)$, obtained as:
%\marginpar{revise solve}
$$solve(t,T)=\left\{
%\mbox{\begin{eqnarray*}
\begin{array}{lll}
\{t=T\}             & \mbox{if} & t \mbox{ is a variable} \\
{\displaystyle \bigcup_{T \longrightarrow f(T_1,\ldots,T_n)}\ \bigcup_{i=1,\ldots,n}}
solve(t_i,T_i)      & \mbox{if} & t \mbox{ is } f(t_1,\ldots,t_n)
\end{array}
%\end{eqnarray*}}
\right.$$

In this abstract interpretation-based setting, analysis with a
monotonic semantic function can be easily
shown correct. However, it is not guaranteed to terminate, since
$\Omega$ has infinite ascending chains. To guarantee termination, a
widening operator is required. 

\begin{08example}
\label{ex:listoflists}
%% Consider the following program which defines the regular type lists of lists of
%% numbers: 
The following program defines the type lists of lists of numbers: 
\begin{verbatim}
list_of_lists([]).                  num_list([]).        
list_of_lists([L|Ls]):-             num_list([N|Xs]):-   
        num_list(L),                        number(N),  
        list_of_lists(Ls).                  num_list(Xs).
\end{verbatim}
For the argument of \texttt{num\_list}, without a widening operator,
an analysis would obtain the following first three approximations:  
$$\begin{array}{rclccrclccrclccrcl}
T_0 & \longrightarrow & [] & & &
T_1 & \longrightarrow & [] \ | \ .(\mathbf{num},T_0) & & &
T_2 & \longrightarrow & [] \ | \ .(\mathbf{num},T_1)
\end{array}$$
where each $T_i$ represents a list of $i$ numbers. Analysis will
never terminate, since it would keep on obtaining a new type
representing a list with one more number. A widening operator would be
required that over-approximates some type $T_l$ to something like
$T_l \longrightarrow [] \ | \ .(\mathbf{num},T_l)$,
%\centerline{$T_l \longrightarrow [] \ | \ .(\mathbf{num},T_l)$}
%\noindent
which is the expected type, and allows termination of the analysis.
\end{08example}


\section{Widenings}
\label{sec:widenings}

%% A widening is required to guarantee that an analysis
%% terminates when the abstract domain has infinite ascending chains as
%% is the case of regular types. 
%% We now revisit widening operators for types proposed in the literature.

%% \begin{definition}[widening operator] \label{def:widening}
%% An operator $\bigtriangledown$ is a widening iff it is:
%%   \begin{description}
%%   \item[correct] $a_1 \sqsubseteq a_1 \bigtriangledown a_1 \wedge
%%     a_2 \sqsubseteq a_1 \bigtriangledown a_2$
%%   \item[stationary] for every increasing chain $a_0 \sqsubset a_1
%%     \sqsubset a_2 \sqsubset \ldots$, the chain $b_0 = a_0, b_1 = b_0
%%     \bigtriangledown a_1, \ldots ,b_{i+1} = b_i \bigtriangledown
%%     a_{i+1}, \ldots$ is not strictly increasing for $\sqsubseteq$,
%%     i.e., there is an $n$ such that $b_n=b_{n+1}$.
%%   \end{description}
%% \end{definition}
%% 
%% For the purposes of termination of the analysis it is enough to
%% require that the widening is stationary for the ascending chains that
%% may occur during analysis of a program.

\paragraph{Functor Widening} \label{sec:widen-de-funct}
This is probably the simplest widening operator which still
keeps information from the recursive structure of the program that
``produces'' the corresponding terms. The idea behind it is to create
a type and a production for each functor symbol in the original type.
All arguments of the function symbols are replaced with the new types~\cite{mildnerthesis}. 

\begin{08example} \label{ex:widen-de-funct}
Consider predicate \texttt{list\_of\_lists} of
Example~\ref{sec:domain}.\ref{ex:listoflists}, its argument should 
ideally have the following type:
%% \begin{eqnarray*}
%%     T_{ll} & \longrightarrow & [] \  | \ .(T_l,T_{ll})  \\
%%     T_l & \longrightarrow & [] \  | \ .(\mathbf{num},T_l) 
%% \end{eqnarray*}
$\begin{array}{lclcclcl}
    T_{ll} & \longrightarrow & [] \  | \ .(T_l,T_{ll}) & & &
    T_l & \longrightarrow & [] \  | \ .(\mathbf{num},T_l) 
\end{array}$
but the functor widening will yield:
$T \longrightarrow [] \ | \ \mathbf{num} \ | \ .(T,T) $.
%% \centerline{$T \longrightarrow [] \ | \ \mathbf{num} \ | \ .(T,T) $}
%\vspace{-2.5\baselineskip}
\end{08example}

\paragraph{Type Jungle Widening} \label{sec:widening-jungla-de}
A type jungle is a grammar where each functor always has the same
arguments. It was originally proposed as a finite type
domain~\cite{lindgrenmildner} , 
since in a domain where all grammars are of the type jungle class
all ascending chains are finite. However, it can be used as a
subdomain to provide a widening %operator.

\begin{08example}
Applying this widening to the previous type $T_{ll}$, the following
will be obtained:
%% \begin{eqnarray*}
%%   T & \longrightarrow & [] \ | \ .(T_1,T)  \\
%%   T_1 & \longrightarrow & [] \ | \ \mathbf{num} \ | \ .(T_1,T)
%% \end{eqnarray*}
\vspace{-\baselineskip}
$$\begin{array}{lclcclcl}
  T & \longrightarrow & [] \ | \ .(T_1,T) & & &
  T_1 & \longrightarrow & [] \ | \ \mathbf{num} \ | \ .(T_1,T)
\end{array}$$
%\vspace{-2.5\baselineskip}
\end{08example}
 
Note that this widening is strictly more precise than the functor
widening. In the example, the new type captures the upper level of
lists, but it loses precision when describing the type of the list
elements. This is due to the restriction of forcing functors to always
have the same arguments. 

\paragraph{Shortening} \label{sec:shortening}
A grammar can be seen as a graph where the nodes correspond to the
non-terminals (or-nodes) and to the right hand sides of productions
(and-nodes), and the edges correspond to the production relation or
the relation between a functor and its arguments in a right hand side
of a production.
%
Given an or-node, its {\em principal functors} are the functors
appearing in its children nodes.

\begin{08example}
The type $T_{ll}$ of the previous examples can be seen as the graph:

\begin{small}
%\vspace{-0.5\baselineskip}
\begin{center}
$
\psmatrix[colsep=9ex,rowsep=1ex]
&                & \mbox{ [ ] }       &             & \mbox{ [ ] } \\
& [mnode=circle] T_{ll} &             & [mnode=circle] T_l & & \mathbf{num} \\
&                & \psframebox{ ./2 } &             & \psframebox{ ./2 } \\
\endpsmatrix 
\psset{nodesep=1pt,arrows=->}
\ncline{2,2}{1,3}
\ncline{2,2}{3,3}
\ncline{3,3}{2,4}
\ncline{2,4}{1,5}
\ncline{2,4}{3,5}
\ncline{3,5}{2,6}
\ncarc[arcangle=110]{3,3}{2,2} 
\ncarc[arcangle=110]{3,5}{2,4} 
$
\end{center}
\end{small}
\end{08example}

Gallagher and de Waal~\cite{gallagher-types-iclp94} defined a widening
which avoids having two or-nodes, which have the same principal functors,
connected by a path. If two such nodes exist, they are replaced
by their least upper bound.

\begin{08example}
In the above example graph, nodes $T_{ll}$ and $T_l$ have the same
principal functors ([] and .) so that they are replaced, yielding:
%% \begin{eqnarray*}
%%   T & \longrightarrow & [] \ | \ .(T_1,T)  \\
%%   T_1 & \longrightarrow & [] \ | \ \mathbf{num} \ | \ .(\mathbf{num},T)
%% \end{eqnarray*}
$$\begin{array}{lclcclcl}
  T & \longrightarrow & [] \ | \ .(T_1,T) & & &
  T_1 & \longrightarrow & [] \ | \ \mathbf{num} \ | \ .(\mathbf{num},T)
\end{array}$$
%\vspace{-2.5\baselineskip}
\end{08example}

Note the precision improvement with respect to the result in the
previous example. Note also that still the result is imprecise.

\paragraph{Restricted Shortening} \label{sec:short-restr}
Saglam and Gallagher~\cite{Saglam-Gallagher-94} propose a more precise
variant of the previous widening. Shortening is restricted so that two
or-nodes $T$ and $T'$ which are connected by a path from $T$ to $T'$
and have the same principal functors are replaced only if 
$T'\sqsubseteq T$. If this is the case, only $T'$ needs be replaced,
since the least upper bound is $T$.  

\begin{08example} \label{ex:short-restr}
Continuing previous examples, since nodes $T_{ll}$ and $T_l$ have
the same principal functors but $T_l \not \sqsubseteq T_{ll}$, 
the widening operation will make no change. In this case, the most
precise type is achieved.
\end{08example}

Note, however, that restricted shortening does not guarantee
termination in general (and thus, it is not, strictly speaking, a
widening). There are cases in which analysis may not 
terminate using only this widening operator~\cite{mildnerthesis}.

\paragraph{Depth Widening}
Janssens and Bruynooghe~\cite{janss92} proposed a type analysis in
which the widening effect is achieved by a ``pruning'' of the type
depth up to a certain bound. A parameter k establishes the maximum
number of occurrences of a functor in-depth in a type. The idea is
similar to the well-known depth-k abstraction for term structure
analysis. The resulting type analysis uses normal restricted type
graphs, which are basically deterministic types satisfying the depth
limit. Obviously, the precision % of this analysis
depends on the value of the parameter k. 

\begin{08example}
The widening of our previous type $T_{ll}$ with k=1 will yield the
same result than the functor widening
(Example~\ref{sec:widenings}.\ref{ex:widen-de-funct}), whereas with
k=2 will yield the same result as restricted shortening
(Example~\ref{sec:widenings}.\ref{ex:short-restr}). 
\vspace{-\baselineskip}
\end{08example}


\paragraph{Topological Clash Widening}
Van Hentenryck et al.~\cite{VanHentenryckCortesiLeCharlier95} proposed
the first widening operator that takes  into account two consecutive
approximations to the type being inferred. After merging the two
---i.e., calculating their least upper bound, the result is compared
with the previous approximation to try to ``guess'' where the type is
growing. This is done by locating {\em topological clashes}: functors
that differ or appear at different depth in each type graph. 
%\marginpar{revise!}
The clashes are resolved by replacing them with the recently
calculated least upper bound. 

\begin{08example}
\label{ex:sorted}
Consider the program:
\begin{verbatim}
sorted([]).
sorted([_X]).
sorted([X,Y|L]):- X =< Y, sorted([Y|L]).
\end{verbatim}
and the moment during analysis when the final widening is performed.
The resulting type for the argument of \texttt{sorted/1}
is the one on the left below for the first two clauses, and the one on
the right for the last one:
$$\begin{array}{lclcclcl}
    T_0 & \longrightarrow & [] \  | \ .(\mathbf{any},[]) & & &
    T_1 & \longrightarrow & .(\mathbf{num},.(\mathbf{num},T_l))  \\
        &                 &                               & & &
    T_l & \longrightarrow & [] \  | \ .(\mathbf{num},T_l) 
\end{array}$$
Their least upper bound is $T_u$ on the left below, which
exhibits a clash with $T_0$ in the second argument of functor $./2$. 
Thus, the result of widening is $T_s$: % on the right:
$$\begin{array}{lclcclcl}
  T_u & \longrightarrow & [] \ | \ .(\mathbf{any},T_l) & & &
  T_s & \longrightarrow & [] \ | \ .(\mathbf{any},T_s)
\end{array}$$
%% \begin{eqnarray*}
%%   T_s & \longrightarrow & [] \ | \ .(\mathbf{any},T_s)
%% \end{eqnarray*}
%\vspace{-1.5\baselineskip}
\end{08example}

All widening operators are based on locating recursive
structures in the type definitions where there are nodes with the same
functors. This may originate an unnecessary loss of precision, since
the widening may impose a recursive structure on the
resulting type in argument positions where the concrete program is in
fact not recursive. In the following section we present a new widening
operator that tries to remedy this problem.

\section{Structural Type Widening}
\label{sec:grammarwithnames}

In this section we define an extended domain for type analysis which
incorporates a widening operator aimed at improving the precision of
the analysis. The domain is defined so as to keep track of information
on the program structure, so that recursion on the types produced by
the analysis is imposed by the widening operator only in the cases
where it corresponds to a recursive structure in the program being
analyzed. To this end, type names will be used.

A \emph{type name} is roughly a (distinguished) non-terminal that
represents a 
type produced during the analysis. Type names are created for each
variable in each argument of each variant of each program atom for
each predicate (note how this is different from, for example,
set-based analyses~\cite{set-based-popl}, where variants are not taken into
account).

Type names provide information on how types are being formed from
other types during analysis. This makes it possible to precisely
identify places where to impose recursion on the types: in a
subterm of the type which happens to refer to the name of that
type. To this end, type names contain 
references to the position of its constituent types. To determine
positions, selectors are used, as defined below.

\begin{definition}[selector]
    Define $t/s$, the subterm of a concrete term $t$ referenced by a
    \emph{selector} $s$, inductively as follows. The empty selector
    $\epsilon$ refers to the term $t$, that is, $t/\epsilon = t$. 
    If $t/s = t'$, $t'$ is a compound term 
    $f(t_1,\ldots,t_i,\ldots,t_n)$ (where $f$ is an $n$-ary function
    symbol) then $t/s\cdot(f.i) = t_i$, $1 \leq i \leq n$. 
\end{definition}

For every two selectors $s$, $p$, if $t/s=t'$ and if $t'/p$ exists
then $t/s\cdot p=t'/p$. The initial $\epsilon$ of a non-empty selector
will often be omitted, so $\epsilon\cdot p$ will be written simply as
$p$. 

We define a set of type names $\mathcal{N}$ such that
$\mathcal{N}\cap\mathcal{G}=\emptyset$ and a set
$\pow{\mathcal{N}\times\mathcal{G}}$ of relations 
$\mathcal{X}\in\pow{\mathcal{N}\times\mathcal{G}}$
between type names and types, of the form
$\mathcal{X}\subseteq\mathcal{N}\times\mathcal{G}$.

\begin{definition}[label]
  Let $\mathcal{X}$ a relation between type names and types. 
  Given a type name $N$, a \emph{label} of $N$ is a tuple
  $\langle s,N' \rangle$, where $s$ is a selector and $N'$ is a
  type name, iff $(N,T)\in\mathcal{X}$, $(N',T')\in\mathcal{X}$, and
  $T' \sqsubseteq T/s$.
%\marginpar{$T/s \sqsubseteq T'$ ??}
\end{definition}

Labels of a type name $N$ indicate subterms of the type $T$ defining
$N$ where other type names occur.

\begin{08example}
Let a relation $\mathcal{X}$ such that $\{ (A,T_1), (B,T_2) \}
\subseteq \mathcal{X}$, and let grammars 
$(T_1,{\cal T}_1,{\cal F},{\cal R}_1)$ and
$(T_2,{\cal T}_2,{\cal F},{\cal R}_2)$, such that
the only rule for $T_1$ is
$(T_1 \longrightarrow f(b))\in {\cal R}_1$ and
$(T_2 \longrightarrow g(c,T_3))\in {\cal R}_2$,
$(T_3 \longrightarrow b ~|~ f(b))\in {\cal R}_2$.
Consider a label $\langle (g.2),A \rangle$ of $B$.
We have that $T_1 \sqsubseteq T_2/(g.2) = T_3$.
\end{08example}
%\vspace{-0.5\baselineskip}

\begin{definition}[type descriptor]
  Let $\mathcal{G}$ a set of types (regular term grammars),
  $\mathcal{N}$ a set of type names, and
  $\mathcal{X}\subseteq\mathcal{N}\times\mathcal{G}$. A
  \emph{type descriptor} is a tuple $(N,E,T)$ where $N\in\mathcal{N}$,
  $T\in\mathcal{G}$, $(N,T)\in\mathcal{X}$, and $E$ is a set of labels
  of $N$. 
\end{definition}

In the new domain, type descriptors will be used instead of types. Let
$\mathcal{D}$ be the set of all type descriptors from given sets of
types $\mathcal{G}$ and of type names $\mathcal{N}$. Concretization is
defined as $\gamma((N,E,T))=\gamma(T)$. The domain ordering and
operations on $\mathcal{D}$ are the same as on $\mathcal{G}$ except
for type names. In this case, they have to take into account the
possible labels of the type name.

%\vspace*{\baselineskip} 
%\begin{nondefinition}[Inclusion]
\paragraph{Inclusion}
%\noindent{\bf Inclusion}
$(N_1,E_1,T_1) \sqsubseteq (N_2,E_2,T_2) \Leftrightarrow 
T_1 \sqsubseteq T_2 \wedge E_1 \subseteq E_2$.

\paragraph{Union}
%\noindent{\bf Union}
$(N,E,T) = (N_1,E_1,T_1) \sqcup (N_2,E_2,T_2) \Leftrightarrow 
T = T_1 \sqcup T_2 \wedge E = E_1 \cup E_2$.

\paragraph{Intersection}
%\noindent{\bf Intersection}
$(N,E,T) = (N_1,E_1,T_1) \sqcap (N_2,E_2,T_2) \Leftrightarrow 
T = T_1 \sqcap T_2 \wedge E = E_1 \cup E_2$.
%\end{nondefinition}
%\vspace*{\baselineskip} 

\paragraph{}
Again, we may be interested in types defined by non-terminals other
than the distinguished non-terminal $T$ of a grammar
$(T,{\cal T},{\cal F},{\cal R})$. A type descriptor $(N_i,E_i,T_i)$,
where $T_i\in{\cal T}$, is formally defined from $(N,E,T)$ as
follows: $T_i$ is the grammar of Equation~\ref{eq:restrict}, $N_i$ is
a new type name, and 
$$E_i = \{ \langle p,N' \rangle ~|~ \langle s\cdot p,N' \rangle \in E
                \wedge T/s = T_i \}.$$

Abstract substitutions for variables of interest $\{x_1,\ldots,x_n\}$
are now defined as tuples of the form
$\langle (N_1,E_1,T_{x_1}),\ldots,(N_n,E_n,T_{x_n})\rangle$. 
Concretization and the domain ordering and operations are lifted to
abstract substitutions element-wise, in the same way as in
Section~\ref{sec:domain}, including the widening operator defined
below. 
%
If now $\Omega$ is the domain of type descriptors, it can be shown
that $(\pow{\Theta},\alpha,\Omega,\gamma)$ is a Galois insertion,
where $\alpha$ is the adjoin of $\gamma$. Abstract unification is
defined as in Equation~\ref{eq:amgu}, but using type descriptors
instead of types (and preserving all type names in the ``input''
abstract substitution $T^n$ to $amgu$).

\begin{definition}[structural widening]
The widening between an approximation $T_2$ to type name $N$ and a
previous approximation $T_1$ to $N$ is
$(N,E_1,T_1) \bigtriangledown (N,E_2,T_2) = (N,E_1 \cup E_2,T)$, such
that $T$ is defined by $(T,{\cal T},{\cal F},{\cal R})$ where 
${\cal T}=\{ T_i ~|~ T \longrightarrow^*_{\cal R} T_i \}$,
and ${\cal R}$ is obtained by the following algorithm:
\end{definition}

\begin{tabbing}
$T'$ := $T_1 \sqcup T_2$ 
        defined by $(T',{\cal T}',{\cal F},{\cal R}')$ \\
$\mathcal{S}$ := $\{ s ~|~ (s,N) \in E_1\cup E_2 \}$ \\
$Seen := \emptyset$ \\
\texttt{for }\=\texttt{each} 
        $(T' \longrightarrow f(A_1,\ldots,A_n))\in {\cal R}'$ 
        \texttt{add to ${\cal R}$ production} \\ 
 \> $T \longrightarrow 
       f(\texttt{widen}(A_1,{\cal R}',(f.1)),\ldots,
         \texttt{widen}(A_n,{\cal R}',(f.n)))$ \\
\\
\texttt{widen}(\=$N,{\cal R}',Sel) :$  \\
\> \texttt{if} $N$ = \textbf{any} \texttt{return} \textbf{any} \\
\> \texttt{if} $\exists M \langle N,M \rangle \in Seen$
  \texttt{return} $M$ \\
\> \texttt{let} $M$ \texttt{a new non-terminal} \\
\> $Seen$ \texttt{:=} $Seen \cup \{ \langle N,M \rangle \}$ \\
\> \texttt{for }\=\texttt{each} 
      $(N \longrightarrow f(A_1,\ldots,A_n))\in {\cal R}'$ 
      \texttt{add to ${\cal R}$ production} \\ 
\> \> $M \longrightarrow 
       f(\texttt{widen}(A_1,{\cal R}',Sel\cdot(f.1)),\ldots,
         \texttt{widen}(A_n,{\cal R}',Sel\cdot(f.n)))$ \\
\> \texttt{if} \= Sel $\in \mathcal{S}$ \texttt{then} \\
\> \> \texttt{add to ${\cal R}$ production} $M \longrightarrow T$ \\
\> \texttt{return} $M$
\end{tabbing} 

Structural widening basically identifies subterms of the new type
$T_1 \sqcup T_2$ where a reference to the type $N$ being widened
appear, and makes this ``self-reference'' explicit in the definition
of the new type. 
%
% Note that the result of the widening, $T$ is a correct over-aproximation of
% $T_2$ since each subterm where a reference to the type $N$ appear is
% equivalent to a previous approximation, which is in turn included in $T_1
% \sqcup T_2$, therefore $T_2 \sqsubseteq (T_1 \sqcup T_2) \sqsubseteq T$ .
%
Note that the widening operation starts with the least upper bound and,
basically, adds new grammar rules to that type. Therefore, the result
is always a correct approximation of such an upper bound. This
justifies its correctness.
%
Moreover, this approach based on type names is potentially more precise
than any of the  previous widening operators discussed, as the
following examples show: 

\begin{08example}
Consider program \texttt{sorted} in Example~\ref{sec:widenings}.\ref{ex:sorted}.
A top-down analysis with topological clash was roughly described there.
Let us now look at analysis using restricted shortening. The resulting
type happens to be the same one.

Analysis of program atom \texttt{sorted([Y|L])} approximates variable
\texttt{Y} always as $\mathbf{num}$, both in the calls and in the
successes. The first two success approximations for variable
\texttt{L} are $[]$ and $.(\mathbf{num},[])$. Their lub (and 
widening) is:
\begin{eqnarray*}
  T_1 & \longrightarrow & [] \ | \ .(\mathbf{num},[])  
\end{eqnarray*}
The next approximation to the type of \texttt{L} is
$.(\mathbf{num},T_1)$. Its lub with $T_1$ is 
$T_2 \longrightarrow [] ~|~ .(\mathbf{num},T_1)$, and since $T_2$ and
$T_1$ have the same functors, and $T_1$ is included in $T_2$, the
widening of $T_2$ is: 
\begin{eqnarray*}
T_3 \longrightarrow [] \ | \ .(\mathbf{num},T_3)  
\end{eqnarray*}
i.e., list of numbers. The next approximation to the type of \texttt{L} 
is $.(\mathbf{num},T_3)$ (i.e., a list with at least one number). It
is included in $T_3$, so fixpoint is reached.

The success of principal goal \texttt{sorted(X)} is approximated
after analyzing the two non-recursive clauses by
$T_4 \longrightarrow [] \ | \ .(\mathbf{any},[])$. Analysis of the
third clause yields $.(\mathbf{num},.(\mathbf{num},T_3))$. Its lub
with $T_4$ is $T_5 \longrightarrow [] \ | \ .(\mathbf{any},T_3)$. The
widening of $T_5$ finds that $T_5$ and $T_3$ have the same functors and
$T_3 \sqsubseteq T_5$, since \textbf{num} $\sqsubseteq$ \textbf{any}.
Thus, the result of widening is:
\begin{eqnarray*}
T_6 \longrightarrow [] \ | \ .(\mathbf{any},T_6)
\end{eqnarray*}
i.e., list of terms. This is the final result after one more 
iteration. Note that the information about successes where the tail of  
lists of length greater than one is a list of numbers is lost.

Let us now consider structural widening. Analysis of atom
\texttt{sorted([Y|L])} always approximates the type of \texttt{Y} by
$(N_{13},\emptyset,\mathbf{num})$. For variable \texttt{L} the two first
approximations are $(N_{14},\emptyset,[])$ and
$(N_{14},E_{14},.(\mathbf{num},[]))$, where the set of labels is
$E_{14} = \{\ (\lcons.1,N_{13}),\ (\lcons.2,N_{14})\ \}$. 
The result of widening is $(N_{14},E_{14},T_1)$ where $T_1$ is defined
as: 
\begin{eqnarray*}
  T_1 & \longrightarrow & [] \ | \ .(\mathbf{num},T_1)
\end{eqnarray*}
i.e., list of numbers. This is the final result after one more
iteration. 

The success of principal goal \texttt{sorted(X)} is approximated
after analyzing the two non-recursive clauses by $(N_3,\emptyset,T_2)$
where $T_2 \longrightarrow [] \ | \ .(\mathbf{any},[])$. Analysis of
the third clause yields
$(N_{3},E_3,.(\mathbf{num},.(\mathbf{num},T_1)))$, where
\begin{eqnarray*}
  E_3 & = & \{\ (\lcons.2\cdot \lcons.1,N_{13}),\
                (\lcons.2\cdot \lcons.2,N_{14})\ \}
\end{eqnarray*}
%\marginpar{$(\lcons.1,N_6)$, $(\lcons.2,N_2)$ ??}
Its widening with the previous approximation $T_2$ is $(N_3,E_3,T_3)$,
where 
\begin{eqnarray*}
  T_3    & \longrightarrow & [] \ | \ .(\mathbf{any},T_1)
%%   E(N_3) & = & \{ (\lcons.1,N_6) , (\lcons.2,N_2) , 
%%                   (\lcons.2\cdot \lcons.1,N_{13}) , 
%%                   (\lcons.2\cdot \lcons.2,N_{14}) \}
\end{eqnarray*}
which amounts to their lub, since the widening operator does not
produce any change, because $N_3$ is not among its own labels.
Therefore, the final result, after one more iteration, is $T_3$,
where indeed lists of length greater than one have a tail which is 
a list of numbers. 
\end{08example}

However, structural widening does not guarantee termination. It is
effective as long as the new approximation is built from the previous
approximation of the type being inferred. This case is identified, in
essence, by locating a reference to the type name of the previous
approximation within the definition of the new one. However, there are
contrived
cases in which a type is constructed during analysis which loses the
reference to the previous approximation. In these cases, a more
restrictive widening has to be applied to guarantee termination.

\begin{08example}
\label{ex:nontermination}
Consider the program:
\begin{verbatim}
main:- p(a).     p(a).                    q(a,f(a)).
                 p(X):- q(X,Y), p(Y).     q(f(Z),f(L)):- q(Z,L).
\end{verbatim}
The calling substitution for atom \texttt{p(Y)} is the sequence
$$\begin{array}{lclcclclcclclccl}
 T_1 & \longrightarrow & f(a) & & &
 T_2 & \longrightarrow & f(f(a)) & & &
 T_3 & \longrightarrow & f(f(f(a))) & & &
 \ldots
\end{array}$$
whereas the type $T \longrightarrow f(a) \ | \ f(T)$ correctly
describes such calls. However, the analysis is not able to infer such
a type.
\end{08example}

The problem in the above example is that none of the approximations
$T_i$ contains a reference to the previous approximation. This is
originated in the program fact for predicate \texttt{q/2} which
causes the loss of the reference to the previous approximation because
of the double occurrence of constant \texttt{a}.

In our analysis, termination is guaranteed by a bound on the number of
times the widening operation can be applied to a type name. A counter
is associated to each type name, so that when the bound is reached
a more restrictive widening that guarantees termination is applied. 

\section{Analysis Results}
\label{sec:results}

We have implemented analyses based on most of the widenings discussed
in this paper, including structural widening. The implementation is in
Prolog and has been incorporated to the CiaoPP
system~\cite{ciaopp-iclp99-tut},
which uses the top-down analysis algorithm of PLAI. The analysis
of~\cite{gallagher-types-iclp94}, based on regular approximations,
which uses a bottom-up algorithm, is also incorporated into the
system. This analysis uses shortening. We want to compare the top-down
and bottom-up approaches with the same widening and similar
implementation technology,\footnote{Similar in the programming
  technique. Of course, the regular approximation method is rather
  different from the method of program interpretation on an abstract
  domain: Evaluating this difference is part of the aim of the
  comparison.}
as well as the precision and efficiency,
within the same analysis framework, of the widening operators
previously discussed. 

We have used two sets of benchmark programs: the one used in the PLAI
framework and that used in the GAIA~\cite{LeCharlier94:toplas} framework.
A summary of the benchmarking follows. The analysis times in
miliseconds are shown in Table~\ref{table:bothfixp} (left). The first column
(\texttt{rul}) is for the regular approximation analysis and the other
three for the PLAI-based analyses: column \texttt{short} for
shortening, column \texttt{clash} for topological clash, and 
column \texttt{struct} for structural widening.

\newcommand{\mejor}{$^*$}

\begin{table}[htbp]
  \begin{center}
    \begin{tabular}{||l||r|r|r|r||} 
\hline \hline 
Program & \multicolumn{1}{|c|}{\texttt{rul}} & 
          \multicolumn{1}{|c|}{\texttt{short}} & 
          \multicolumn{1}{|c|}{\texttt{clash}} & 
          \multicolumn{1}{|c||}{\texttt{struct}} \\
\hline \hline 
aiakl       &  568&        469&        529&      900 \\
bid         & 1480&       2209&       2529&     4730 \\
boyer       & 3450&       3890&       4989&     9629 \\
browse      &  758&        380&        389&      539 \\
cs\_o       & 3840&       1889&       2689&     2580 \\
cs\_r       &18549&      10720&      24479&    19560 \\
disj\_r     & 4468&       1819&       6399&     2440 \\
gabriel     & 1549&       1430&       1870&     1760 \\
grammar     &  330&        160&        160&      190 \\
hanoiapp    &  620&        719&       1889&     1150 \\
kalah\_r    & 1520&         79&         79&       89 \\
mmatrix     &  310&        190&        209&      119 \\
occur       &  380&        219&        330&      289 \\
palin       &  590&        840&        980&      850 \\
pg          &  839&       2020&       2980&     3990 \\
plan        & 1138&        819&        960&     1009 \\
progeom     &  979&       1840&       2530&     3640 \\
qsort       &  310&        590&        659&      680 \\
qsortapp    &  369&       1000&       2898&     1210 \\
queens      &  329&        179&        190&      180 \\
query       &  720&        360&        370&      410 \\
serialize   &  478&        810&        969&      899 \\
witt        & 2929&       4890&       1399&     1169 \\
zebra       &  560&       3490&      14958&    12830 \\
\hline \hline 
\multicolumn{5}{c}{(excluding simplification times)}
    \end{tabular}\hfill
    \begin{tabular}{||l||r|r|r|r||} 
\hline \hline 
Program & \multicolumn{1}{|c|}{\texttt{rul}} & 
          \multicolumn{1}{|c|}{\texttt{short}} & 
          \multicolumn{1}{|c|}{\texttt{clash}} & 
          \multicolumn{1}{|c||}{\texttt{struct}} \\
\hline \hline 
aiakl       &        697&       3009&       3738&     1409 \\
bid         &       2899&      31278&      35949&    15259 \\
boyer       &      19620&     201169&     206917&    92117 \\
browse      &        987&       2848&       2987&     1698 \\
cs\_o       &      11958&      17389&      32959&     4878 \\
cs\_r       &      50760&     303430&     238788&    30169 \\
disj\_r     &       6508&      18598&      26077&     6408 \\
gabriel     &       2098&      13388&      22379&     5208 \\
grammar     &        759&       3169&       3169&     1279 \\
hanoiapp    &        840&       3988&      13738&     3378 \\
kalah\_r    &       2069&       1187&       1188&      888 \\
mmatrix     &        757&       1769&       2078&      488 \\
occur       &        530&       1647&       2628&      767 \\
palin       &        997&       8520&      11878&     2180 \\
pg          &       1349&      15380&      22870&     7370 \\
plan        &       1587&       6167&       6559&     2288 \\
progeom     &       1358&      12800&      17598&     6679 \\
qsort       &        520&       3439&       4168&     1409 \\
qsortapp    &        569&       7789&       9669&     2900 \\
queens      &        457&       1128&       1138&      429 \\
query       &       1627&      22458&      22788&    11818 \\
serialize   &        937&       8429&      11957&     2217 \\
witt        &       3438&     188419&      42699&    25709 \\
zebra       &        717&      55100&     189949&    44540 \\
\hline \hline
\multicolumn{5}{c}{(including simplification times)}
    \end{tabular}
    \caption{Timing results}
    \label{table:bothfixp}
    \label{table:bothsimp}
  \end{center}
\vspace{-2.5\baselineskip}
\end{table}

Table~\ref{table:precision} shows results in terms of precision.
The precision of \texttt{struct} is never improved by any of the
others. The improved precision of \texttt{struct} has been measured
as follows. The left subcolumns under \texttt{rul}, \texttt{short}, and
\texttt{clash} show the number of types with a more precise definition
inferred by \texttt{struct}. The right subcolumns show the number of types 
where the previous ones appear (and are thus, also, more precise).
The former are types directly inferred from program predicates; the
latter are types which are defined from the former, due to the data
flow in the program.

\begin{table}[htbp]
  \begin{center}
    \begin{tabular}{||l||r|r||r|r||r|r||r||}
\hline \hline 
Program & \multicolumn{2}{|c||}{\texttt{rul}} & 
          \multicolumn{2}{|c||}{\texttt{short}} & 
          \multicolumn{2}{|c||}{\texttt{clash}} \\
\hline \hline 
aiakl          & 1 & 1 & 1 & 1  &   &    \\  
bid            & 9 & 12& 9 & 12 &   &    \\
cs\_o          & 4 & 18& 4 & 18 & 2 & 9  \\
cs\_r          & 4 & 28& 4 & 28 & 2 & 19 \\
disj\_r        & 6 & 13& 6 & 13 &   &    \\
mmatrix        & 2 & 2 & 2 & 2  &   &    \\
occur          & 1 & 1 & 1 & 1  &   &    \\
palin          & 2 & 4 & 2 & 4  &   &    \\
pg             & 1 & 1 & 1 & 1  &   &    \\
qsort          & 1 & 1 & 1 & 1  &   &    \\
serialize      & 2 & 4 & 2 & 4  &   &    \\
zebra          & 3 & 3 & 3 & 3  & 1 & 1  \\
\hline \hline 
    \end{tabular}
    \caption{Precision results}
    \label{table:precision}
  \end{center}
\vspace{-2\baselineskip}
\end{table}

%% Also, mention the times the bound on the number of widenings is
%% reached... 

The following conclusions can be drawn from the tables. First, the
regular approximation approach seems to behave better in terms of
efficiency than the program interpretation approach, at least for the
bigger programs. This conclusion, however, has to be taken with some
care, since the current implementation of \texttt{rul} performs some
caching of the type grammars that the PLAI-based analysis does
not. % The effect of 
This should be subject of a more thorough
evaluation, which is out of the scope of this paper. The fact that it
improves in bigger programs seems to suggest that the effect of this
caching is most surely not negligible.

Regarding the analyses based on program interpretation, it can be
concluded that the better the precision the worse the efficiency:
\texttt{short} takes less than \texttt{clash}, and this one takes less
than \texttt{struct}; this one is more precise than \texttt{clash},
which is more precise than \texttt{short}. This conclusion seems
evident at first sight, but it is not: in analysis, an improvement in
precision can very well trigger an improvement in efficiency. This can
also be seen in the tables in some cases, the most significant
probably being \texttt{zebra}. % in table~\ref{table:ciaoppfixp}.
Overall, one can arguably conclude that the efficiency loss found is
not a high price in exchange for the gain in precision.
%\marginpar{discuss results!}

We have also carried out another test.
For practical purposes, the CiaoPP system includes a back-end to the
analysis that simplifies the types inferred, in the sense that
equivalent types are identified, so that they are then reduced to a
single type. This facilitates the interpretation of the output. 
%
It is the case that the structural widening includes certain amount of
type simplification, so that the analysis creates less different types
which are in fact equivalent. For this reason, we have included the
same tests as above, but adding now the times taken in the back-end
simplification phase. 

The times including the simplification are shown in
table~\ref{table:bothsimp}. The columns
read as before. It can be seen that in this case structural widening
outperforms all of the other analyses, except, in some cases,
\texttt{rul}. 
%
It also can be observed that \texttt{rul} behaves usually better than
\texttt{short} also when simplification is included. This seems to
suggest that incorporating our widening into the regular approximation
approach would probably give the best results in practice.\footnote{This,
  however, may not be trivial. It is subject for future work.} 


\section{Conclusions}
\label{sec:conclusions}

We have presented a new widening operator on regular types within
an abstract interpretation-based characterization of type inference.
The idea behind it is similar to set-based
analyses~\cite{FruewirthShapiroVardiYardeni91,set-based-popl} in that
we assign and fix type names, but it is applied here with more generality.
It can be seen as a generalization of the idea of ``guessing'' the
growth of the types during analysis which is
behind~\cite{VanHentenryckCortesiLeCharlier95}. Instead of guessing,
our technique determines exactly where the type is growing.
%
The resulting widening operator has been presented on deterministic
regular types. However, its extension to non-deterministic regular
types should be straightforward.

Our operator is more precise than previous approaches,
but it is still efficient. This has been shown with (preliminary)
practical results. However, it does not guarantee termination. We are
currently working on the non-termination problem. A moded type domain
will help in this. The idea is to enhance abstract unification so that
it is able to identify the ``transference'' of type names from the
input to the output types, so that the names are not dropped. This
will remedy the problem of Example~\ref{ex:nontermination} and,
hopefully, allow us to prove termination of analyses with the proposed
widening operator.

Finally, this work has revealed two issues that may be worth
investigating for practical purposes: the impact on the
efficiency of analysis of the different implementation techniques
for different analysis methods,
%(e.g., regular approximations versus program interpretation),
on one hand, and of the simplification of
types, on the other hand. 

\paragraph{\bf Acknowledgements}
%
We would like to thank John Gallagher for very useful discussions, and
Pedro L\'{o}pez for his help with the implementation and the
availability of his library on type manipulation.
This work has been partially supported by Spanish MCYT project EDIPIA
TIC99-1151.

\begin{thebibliography}{10}

\bibitem{set-based-popl}
W.~Charatonik, A.~Podelski, and J.-M. Talbot.
\newblock {P}aths vs. {T}ress in {S}et-based {P}rogram {A}nalysis.
%\newblock In {\em Principles of Programming Languages}, pages 330--338. {ACM}
\newblock In {\em POPL00}, pages 330--338. {ACM}
  {P}ress, January 2000.

\bibitem{LeCharlier94:toplas}
B.~Le Charlier and P.~{Van Hentenryck}.
\newblock {E}xperimental {E}valuation of a {G}eneric {A}bstract
  {I}nterpretation {A}lgorithm for {P}rolog.
\newblock {\em ACM Transactions on Programming Languages and Systems},
  16(1):35--101, 1994.

\bibitem{Dart-Zobel}
P.W. Dart and J.~Zobel.
\newblock {A} {R}egular {T}ype {L}anguage for {L}ogic {P}rograms.
\newblock In F.~Pfenning, editor, {\em {T}ypes in {L}ogic {P}rogramming}, pages
  157--187. MIT Press, 1992.

\bibitem{FruewirthShapiroVardiYardeni91}
T.~Fr{\"u}wirth, E.~Shapiro, M.Y. Vardi, and E.~Yardeni.
\newblock Logic programs as types for logic programs.
\newblock In {\em Proc. LICS'91}, pages 300--309, 1991.

\bibitem{gallagher-types-iclp94}
J.P. Gallagher and D.A. de~Waal.
\newblock Fast and precise regular approximations of logic programs.
\newblock In Pascal {Van~Hentenryck}, editor, {\em Proc.~of the 11th
  International Conference on Logic Programming}, pages 599--613. MIT Press,
  1994.

\bibitem{ciaopp-iclp99-tut}
M.~Hermenegildo, F.~Bueno, G.~Puebla, and P.~L\'{o}pez-Garc\'{\i}a.
\newblock {P}rogram {A}nalysis, {De}bugging and {O}ptimization {U}sing the
  {C}iao {S}ystem {P}reprocessor.
%\newblock In {\em 1999 International Conference on Logic Programming}, pages
\newblock In {\em ICLP99}, pages
  52--66, Cambridge, MA, November 1999. MIT Press.

\bibitem{janss92}
G.~Janssens and M.~Bruynooghe.
\newblock Deriving {D}escriptions of {P}ossible {V}alues of {P}rogram
  {V}ariables by means of {A}bstract {I}nterpretation.
\newblock {\em Journal of Logic Programming}, 13(2 and 3):205--258, July 1992.

\bibitem{lindgrenmildner}
T.~Lindgren and P.~Mildner.
\newblock The impact of structure analysis on prolog compilation.
\newblock Tech.\ Rep.\ 140, Computing Science Dept., Uppsala
  University, 1997.

\bibitem{mildnerthesis}
P.~Mildner.
\newblock {\em Type Domains for Abstract Interpretation: A Critical Study}.
\newblock PhD thesis, Computing Science Department - Uppsala University, 1999.

\bibitem{Saglam-Gallagher-94}
H.~Saglam and J.~Gallagher.
\newblock Approximating logic programs using types and regular descriptions.
\newblock Tech.\ Rep.\ CSTR-94-19, Dept.\ of C.\ Science,
  U.\ of Bristol, 1994.

\bibitem{VanHentenryckCortesiLeCharlier95}
P.~Van~Hentenryck, A.~Cortesi, and B.~Le~Charlier.
\newblock Type analysis of prolog using type graphs.
\newblock {\em Journal of Logic Programming}, 22(3):179--209, 1995.

\end{thebibliography}

\end{document}

pst-3d.tex
%% BEGIN pst-3d.tex
%%
%% Tilting and other pseudo-3D tricks with PSTricks 97.
%% There is not any documentation.
%%
\def\fileversion{97}
\def\filedate{1997/03/25}
%%
%% COPYRIGHT 1993, 1994, 1999 by Timothy Van Zandt, tvz@nwu.edu.
%%
%% This program can be redistributed and/or modified under the terms
%% of the LaTeX Project Public License Distributed from CTAN
%% archives in directory macros/latex/base/lppl.txt.
%%
\message{ v\fileversion, \filedate}

\csname PSTthreeDLoaded\endcsname
\let\PSTthreeDLoaded\endinput

\ifx\PSTricksLoaded\endinput\else
  \def\next{\input pstricks.tex}
  \expandafter\next
\fi

\edef\TheAtCode{\the\catcode`\@}
\catcode`\@=11

% \begin{macro}{\tx@SetMatrixThreeD,\tx@ProjThreeD,\tx@SetMatrixEmbed}
% Viewpoint for 3D coordinates is given by three angles: $\alpha$, $\beta$ and
% $\gamma$. $\alpha$ and $\beta$ determine the direction from which one is
% looking. $\gamma$ then determines the orientation of the observing.
%
% When $\alpha$, $\beta$ and $\gamma$ are all zero, the observer is looking
% from the negative part of the $y$-axis, and sees the $xz$-plane the way in
% 2D one sees the $xy$ plan. Hence, to convert the 3D coordinates to their 2D
% project, $\la x, y, z\ra$ map to $\la x, z\ra$.
%
% When the orientation is different, we rotate the coordinates, and then
% perform the same projection.
%
% We move up to latitude $\beta$, over to longitude $\alpha$, and then rotate
% by $\gamma$. This means that we first rotate around $y$-axis by $\gamma$,
% then around $x$-axis by $\beta$, and the around $z$-axis by $\alpha$.
%
% Here are the matrices:
% \begin{eqnarray*}
%   R_z(\alpha) & = & \left[
%     \begin{array}{ccc}
%       \cos \alpha & -\sin \alpha & 0 \\
%       \sin \alpha & cos \alpha   & 0 \\
%       0           & 0            & 1
%     \end{array} \right] \\
%   R_x(\beta) & = & \left[
%     \begin{array}{ccc}
%       1           & 0            & 0 \\
%       0           & \cos \beta   & \sin \beta \\
%       0           & -\sin \beta  & \cos \beta
%     \end{array} \right] \\
%   R_y(\gamma) & = & \left[
%     \begin{array}{ccc}
%       \cos \gamma & 0            & -\sin \gamma \\
%       0           & 1            & 0 \\
%       \sin \gamma & 0            & \cos \gamma
%     \end{array} \right]
% \end{eqnarray*}
%
% The rotation of a coordinate is then performed by the matrix $R_z(\alpha)
% R_x(\beta) R_y(\gamma)$. The first and third columns of the matrix are the
% basis vectors of the plan upon which the 3D coordinates are project (the old
% basis vectors were $\la 1, 0, 0\ra$ and $\la 0, 0, 1$\ra; rotating these
% gives the first and third columns of the matrix).
%
% These new basis vectors are:
% \begin{eqnarray*}
%   \tilde{x} & = & \left[
%     \begin{array}{c}
%       \cos\alpha \cos\gamma - \sin\beta \sin\alpha \sin\gamma \\
%       \sin\alpha \cos\gamma + \sin\beta \cos\alpha \sin\gamma \\
%       \cos\beta \sin\gamma
%     \end{array} \right] \\
%   \tilde{z} & = & \left[
%     \begin{array}{c}
%       -\cos\alpha \sin\gamma - \sin\beta \sin\alpha \cos\gamma \\
%       -\sin\alpha \sin\gamma + \sin\beta \cos\alpha \cos\gamma \\
%       \cos\beta \cos\gamma
%     \end{array} \right]
% \end{eqnarray*}
%
% Rather than specifying the angles $\alpha$ and $\beta$, the user gives a
% vector indicating where the viewpoint is. This new viewpoint is the rotation
% o the old viewpoint. The old viewpoint is $\la 0, -1, 0\ra$, and so the new
% viewpoint is
% \[
%  R_z(\alpha) R_x(\beta) \left[ \begin{array}{c} 0\\-1\\0 \end{array} \right]
%  \, = \,
%  \left[ \begin{array}{c}
%    \cos\beta \sin\alpha \\
%    -\cos\beta \cos\alpha \\
%    \sin\beta
%  \end{array} \right]
%  \, = \,
%  \left[ \begin{array}{c} v_1 \\ v_2 \\ v_3 \end{array} \right]
% \]
% Therefore,
% \begin{eqnarray*}
%   \alpha & = & \arc\tan (v_1 / -v_2) \\
%   \beta & = & \arc\tan (v_3 \sin\alpha / v_1)
% \end{eqnarray*}
% Unless $p_1=p_2=0$, in which case $\alpha=0$ and $\beta=\sign(p_3)90$, or
% $p_1=p_3=0$, in which case $\beta=0$.
%
% The syntax of "SetMatrixThreeD" is
% \begin{Ex}
%   $v_1$ $v_2$ $v_3$ $\gamma$ "SetMatrixThreeD"
% \end{Ex}
% "SetMatrixThreeD" first computes
% \[
%   \begin{array}{ll}
%     a=\sin\alpha & b=\cos\alpha\\
%     c=\sin\beta  & d=\cos\beta\\
%     e=\sin\gamma & f=\cos\gamma
%   \end{array}
% \]
% and then sets "Matrix3D" to "["$\tilde{x}$ $\tilde{z}$"]".
%
%    \begin{macrocode}
\pst@def{SetMatrixThreeD}<%
  dup sin /e ED cos /f ED
  /p3 ED /p2 ED /p1 ED
  p1 0 eq
  { /a 0 def /b p2 0 le { 1 } { -1 } ifelse def
    p3 p2 abs
  }
  { p2 0 eq
    { /a p1 0 lt { -1 } { 1 } ifelse def /b 0 def
      p3 p1 abs
    }
    { p1 dup mul p2 dup mul add sqrt dup
      p1 exch div /a ED
      p2 exch div neg /b ED
      p3 p1 a div
    }
    ifelse
  }
  ifelse
  atan dup sin /c ED cos /d ED
  /Matrix3D
  [
    b f mul c a mul e mul sub
    a f mul c b mul e mul add
    d e mul
    b e mul neg c a mul f mul sub
    a e mul neg c b mul f mul add
    d f mul
  ] def>
%    \end{macrocode}
%
% The syntax of "ProjThreeD" is
% \begin{Ex}
%   $x$ $y$ $z$ ProjThreeD $x'$ $y'$
% \end{Ex}
% where $x'=\la x, y, z\ra \cdot \tilde{x}$ and $y'=\la x, y, z\ra \cdot
% \tilde{z}$.
%
%    \begin{macrocode}
\pst@def{ProjThreeD}<%
  /z ED /y ED /x ED
  Matrix3D aload pop
  z mul exch y mul add exch x mul add
  4 1 roll
  z mul exch y mul add exch x mul add
  exch>
%    \end{macrocode}
%
% To embed 2D $\la x, y\ra$ coordinates in 3D, the user specifies the normal
% vector and an angle. If we decompose this normal vector into an angle, as
% when converting 3D coordinates to 2D coordinates, and let $\hat\alpha$,
% $\hat\beta$ and $\hat\gamma$ be the three angles, then when these angles are
% all zero the coordinate $\la x, y\ra$ gets mapped to $\la x, 0, y\ra$, and
% otherwise $\la x, y\ra$ gets mapped to
% \[
%   R_z(\hat\alpha) R_x(\hat\beta) R_y(\hat\gamma)
%   \left[ \begin{array}{c} x \\ 0 \\ y \end{array} \right]
%  \, = \,
%   \left[ \begin{array}{c}
%    \hat{x}_1 x + \hat{z}_1 y\\
%    \hat{x}_2 x + \hat{z}_2 y\\
%    \hat{x}_3 x + \hat{z}_3 y
%   \end{array} \right]
% \]
% where $\hat{x}$ and $\hat{z}$ are the first and third columns of
% $R_z(\hat\alpha) R_x(\hat\beta) R_y(\hat\gamma)$.
%
% Now add on a 3D-origin:
% \[
%   \left[ \begin{array}{c}
%    \hat{x}_1 x + \hat{z}_1 y + x_0\\
%    \hat{x}_2 x + \hat{z}_2 y + y_0\\
%    \hat{x}_3 x + \hat{z}_3 y + z_0
%   \end{array} \right]
% \]
%
% Now when we project back onto 2D coordinates, we get
% \begin{eqnarray*}
%   x' & = & \tilde{x}_1(\hat{x}_1 x + \hat{z}_1 y + x_0) +
%            \tilde{x}_2(\hat{x}_2 x + \hat{z}_2 y + y_0) +
%            \tilde{x}_3(\hat{x}_3 x + \hat{z}_3 y + z_0)\\
%   & = &
%   (\tilde{x}_1\hat{x}_1 + \tilde{x}_2\hat{x}_2 + \tilde{x}_3\hat{x}_3) x\\
%   + (\tilde{x}_1\hat{z}_1 + \tilde{x}_2\hat{z}_2 + \tilde{x}_3\hat{z}_3) y\\
%   + \tilde{x}_1 x_0 + \tilde{x}_2 y_0 + \tilde{z}_3 z_0
%   y' & = & \tilde{z}_1(\hat{x}_1 x + \hat{z}_1 y + x_0) +
%            \tilde{z}_2(\hat{x}_2 x + \hat{z}_2 y + y_0) +
%            \tilde{z}_3(\hat{x}_3 x + \hat{z}_3 y + z_0)\\
%   & = &
%   (\tilde{z}_1\hat{x}_1 + \tilde{z}_2\hat{x}_2 + \tilde{z}_3\hat{x}_3) x\\
%   + (\tilde{z}_1\hat{z}_1 + \tilde{z}_2\hat{z}_2 + \tilde{z}_3\hat{z}_3) y\\
%   + \tilde{z}_1 x_0 + \tilde{z}_2 y_0 + \tilde{z}_3 z_0
% \end{eqnarray*}
% Hence, the transformation matrix is:
% \[
%   \left[ \begin{array}{c}
%   \tilde{x}_1\hat{x}_1 + \tilde{x}_2\hat{x}_2 + \tilde{x}_3\hat{x}_3) \\
%   \tilde{z}_1\hat{x}_1 + \tilde{z}_2\hat{x}_2 + \tilde{z}_3\hat{x}_3) \\
%   \tilde{x}_1\hat{z}_1 + \tilde{x}_2\hat{z}_2 + \tilde{x}_3\hat{z}_3) \\
%   \tilde{z}_1\hat{z}_1 + \tilde{z}_2\hat{z}_2 + \tilde{z}_3\hat{z}_3) \\
%   \tilde{x}_1 x_0 + \tilde{x}_2 y_0 + \tilde{z}_3 z_0 \\
%   \tilde{z}_1 x_0 + \tilde{z}_2 y_0 + \tilde{z}_3 z_0
%   \end{array} \right]
% \]
%
% The syntax of "SetMatrixEmbed" is
% \begin{Ex}
%   $x_0$ $y_0$ $z_0$ $\hat{v_1}$ $\hat{v_2}$ $\hat{v_3} $\hat{\gamma}$
%   $v_1$ $v_2$ $v_3$ $\gamma$ "SetMatrixEmbed"
% \end{Ex}
% "SetMatrixEmbed" first sets "<x1 x2 x3 y1 y2 y3>" to the basis vectors for
% the viewpoint projection (the tilde stuff above). Then it sets "Matrix3D" to
% the basis vectors for the embedded plane. Finally, it sets the
% transformation matrix to the matrix given above.
%
%    \begin{macrocode}
\pst@def{SetMatrixEmbed}<%
  \tx@SetMatrixThreeD
  Matrix3D aload pop
  /z3 ED /z2 ED /z1 ED /x3 ED /x2 ED /x1 ED
  \tx@SetMatrixThreeD
  [
  Matrix3D aload pop
  z3 mul exch z2 mul add exch z1 mul add 4 1 roll
  z3 mul exch z2 mul add exch z1 mul add
  Matrix3D aload pop
  x3 mul exch x2 mul add exch x1 mul add 4 1 roll
  x3 mul exch x2 mul add exch x1 mul add
  3 -1 roll 3 -1 roll 4 -1 roll 8 -3 roll 3 copy
  x3 mul exch x2 mul add exch x1 mul add 4 1 roll
  z3 mul exch z2 mul add exch z1 mul add
  ]
  concat>
%   \end{macrocode}
% \end{macro}
%
% \begin{macro}{\psset@viewpoint,\psk@viewpoint}
%    \begin{macrocode}
\let\pssetzlength\pssetylength
\def\psset@viewpoint#1{%
  \pst@expandafter\psset@@viewpoint#1 {} {} {} \@nil
  \let\psk@viewpoint\pst@tempg}
\def\psset@@viewpoint#1 #2 #3 #4\@nil{%
  \begingroup
    \pssetxlength\pst@dima{#1}%
    \pssetylength\pst@dimb{#2}%
    \pssetzlength\pst@dimc{#3}%
    \xdef\pst@tempg{%
      \pst@number\pst@dima \pst@number\pst@dimb \pst@number\pst@dimc}%
  \endgroup}
\psset@viewpoint{1 -1 1}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\psset@viewangle,\psk@viewangle}
%    \begin{macrocode}
\def\psset@viewangle#1{\pst@getangle{#1}\psk@viewangle}
\psset@viewangle{0}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\psset@normal,\psk@normal}
%    \begin{macrocode}
\def\psset@normal#1{%
  \pst@expandafter\psset@@viewpoint#1 {} {} {} \@nil
  \let\psk@normal\pst@tempg}
\psset@normal{0 0 1}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\psset@embedangle,\psk@embedangle}
%    \begin{macrocode}
\def\psset@embedangle#1{\pst@getangle{#1}\psk@embedangle}
\psset@embedangle{0}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\tx@TMSave,\tx@TMRestore}
% \begin{LVerbatim}
%   {<Proc for modifying tm>} TMChange
%    \begin{macrocode}
\pst@def{TMSave}<%
  tx@Dict /TMatrix known not { /TMatrix { } def /RAngle { 0 } def } if
  /TMatrix [ TMatrix CM ] cvx def>
\pst@def{TMRestore}<%
  CP /TMatrix [ TMatrix setmatrix ] cvx def moveto>
\pst@def{TMChange}<%
  \tx@TMSave
  /cp [ currentpoint ] cvx def % ??? Check this later.
  CM
% Set "standard" coor. system , with "pt" units and origin at currentpoint.
% This let's us rotate, or whatever, around \TeX's current point, without
% having to worry about strange coordinate systems that the dvi-to-ps
% driver might be using.
  CP T \tx@STV
% Let M = old matrix (on stack), and M' equal current matrix. Then
% go from M' to M by applying  M Inv(M').
  CM matrix invertmatrix    % Inv(M')
  matrix concatmatrix       % M Inv(M')
% Now modify transformation matrix:
  exch exec
% Now apply M Inv(M')
  concat cp moveto>
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\ThreeDput}
%    \begin{macrocode}
\def\ThreeDput{\def\pst@par{}\pst@object{ThreeDput}}
\def\ThreeDput@i{\@ifnextchar({\ThreeDput@ii}{\ThreeDput@ii(\z@,\z@,\z@)}}
\def\ThreeDput@ii(#1,#2,#3){%
  \pst@killglue\pst@makebox{\ThreeDput@iii(#1,#2,#3)}}
\def\ThreeDput@iii(#1,#2,#3){%
  \begingroup
    \use@par
    \if@star\pst@starbox\fi
    \pst@makesmall\pst@hbox
    \pssetxlength\pst@dima{#1}%
    \pssetylength\pst@dimb{#2}%
    \pssetzlength\pst@dimc{#3}%
    \leavevmode
    \hbox{%
      \pst@Verb{%
        { \pst@number\pst@dima
          \pst@number\pst@dimb
          \pst@number\pst@dimc
          \psk@normal
          \psk@embedangle
          \psk@viewpoint
          \psk@viewangle
          \tx@SetMatrixEmbed
        } \tx@TMChange}%
    \box\pst@hbox
    \pst@Verb{\tx@TMRestore}}%
  \endgroup
  \ignorespaces}
%    \end{macrocode}
% \end{macro}
%
%
% \section{Arithmetic\label{Arithmetic}}
%
%
% \begin{macro}{\pst@divide}
% This is adapted from Donald Arseneau's "shapepar.sty".
% Syntax:
% \begin{LVerbatim}
%   \pst@divide{<numerator>}{<denominator>}{<command>}
%   \pst@@divide{<numerator>}{<denominator>}
% \end{LVerbatim}
% <numerator> and <denominator> should be dimensions. "\pst@divide" sets
% <command> to <num>/<den> (in points). "\pst@@divide" sets "\pst@dimg" to
% <num>/<den>.
%    \begin{macrocode}
\def\pst@divide#1#2#3{%
  \pst@@divide{#1}{#2}%
  \pst@dimtonum\pst@dimg{#3}}
\def\pst@@divide#1#2{%
  \pst@dimg=#1\relax
  \pst@dimh=#2\relax
  \pst@cntg=\pst@dimh
  \pst@cnth=67108863
  \pst@@@divide\pst@@@divide\pst@@@divide\pst@@@divide
  \divide\pst@dimg\pst@cntg}
%    \end{macrocode}
% The number 16 is the level of uncertainty. Use a lower power of 2 for more
% accuracy (2 is most precise). But if you change it, you must change the
% repetions of "\pst@@@divide" in "\pst@@divide" above:
% \[
%   \mbox{precision}^\mbox{repetitions} = 65536
% \]
% (E.g., $16^4 = 65536$).
%    \begin{macrocode}
\def\pst@@@divide{%
  \ifnum
    \ifnum\pst@dimg<\z@-\fi\pst@dimg<\pst@cnth
    \multiply\pst@dimg\sixt@@n
  \else
    \divide\pst@cntg\sixt@@n
  \fi}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pst@pyth}
% Syntax:
% \begin{LVerbatim}
%   \pst@pyth{<dim1>}{<dim2>}{<dimen register>}
% \end{LVerbatim}
% <dimen register> is set to $((dim1)^2+(dim2)^2)^{1/2}$.
%
% The algorithm is copied from \PiCTeX, by Michael Wichura (with permission).
% Here is his description:
% \begin{quote}
% Suppose $x>0$, $y>0$. Put $s = x+y$. Let $z = (x^2+y^2)^{1/2}$. Then $z =
% s\times f$, where
% \[
%   f = (t^2 + (1-t)^2)^{1/2} = ((1+\tau^2)/2)^{1/2}
% \]
% and $t = x/s$  and  $\tau = 2(t-1/2)$.
% \end{quote}
%    \begin{macrocode}
\def\pst@pyth#1#2#3{%
  \begingroup
    \pst@dima=#1\relax
    \ifnum\pst@dima<\z@\pst@dima=-\pst@dima\fi  % dima=abs(x)
    \pst@dimb=#2\relax
    \ifnum\pst@dimb<\z@\pst@dimb=-\pst@dimb\fi  % dimb=abs(y)
    \advance\pst@dimb\pst@dima         % dimb=s=abs(x)+abs(y)
    \ifnum\pst@dimb=\z@
      \global\pst@dimg=\z@             % dimg=z=sqrt(x^2+y^2)
    \else
      \multiply\pst@dima 8\relax              % dima= 8abs(x)
      \pst@@divide\pst@dima\pst@dimb     % dimg =8t=8abs(x)/s
      \advance\pst@dimg -4pt            % dimg = 4tau = (8t-4)
      \multiply\pst@dimg 2
      \pst@dimtonum\pst@dimg\pst@tempa
      \pst@dima=\pst@tempa\pst@dimg           % dima=(8tau)^2
      \advance\pst@dima 64pt         % dima=u=[64+(8tau)^2]/2
      \divide\pst@dima 2\relax                      % =(8f)^2
      \pst@dimd=7pt                % initial guess at sqrt(u)
      \pst@@pyth\pst@@pyth\pst@@pyth            % dimd=sqrt(u)
      \pst@dimtonum\pst@dimd\pst@tempa
      \pst@dimg=\pst@tempa\pst@dimb
      \global\divide\pst@dimg 8             % dimg=z=(8f)*s/8
    \fi
  \endgroup
  #3=\pst@dimg}
\def\pst@@pyth{%                      dimd = g <-- (g + u/g)/2
  \pst@@divide\pst@dima\pst@dimd
  \advance\pst@dimd\pst@dimg
  \divide\pst@dimd 2\relax}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pst@sinandcos}
% Syntax:
% \begin{LVerbatim}
%   \pst@sinandcos{<dim>}{<int>}
% \end{LVerbatim}
% <dim>, in "sp" units, should equal 100,000 times the angle, in degrees
% between 0 and 90. <int> should equal the angle's quadrant (0, 1, 2 or 3).
% "\pst@dimg" is set to $\sin(\theta)$ and "\pst@dimh" is set to
% $\cos(\theta)$ (in pt's).
%
% The algorithms uses the usual McLaurin expansion.
%    \begin{macrocode}
\def\pst@sinandcos#1{%
  \begingroup
    \pst@dima=#1\relax
    \pst@dima=.366022\pst@dima     %Now 1pt=1/32rad
    \pst@dimb=\pst@dima   % dimb->32sin(angle) in pts
    \pst@dimc=32\p@       % dimc->32cos(angle) in pts
    \pst@dimtonum\pst@dima\pst@tempa
    \pst@cntb=\tw@
    \pst@cntc=-\@ne
    \pst@cntg=32
    \loop
    \ifnum\pst@dima>\@cclvi % 256
      \pst@dima=\pst@tempa\pst@dima
      \divide\pst@dima\pst@cntg
      \divide\pst@dima\pst@cntb
      \ifodd\pst@cntb
        \advance\pst@dimb \pst@cntc\pst@dima
        \pst@cntc=-\pst@cntc
      \else
        \advance\pst@dimc by \pst@cntc\pst@dima
      \fi
      \advance\pst@cntb\@ne
    \repeat
    \divide\pst@dimb\pst@cntg
    \divide\pst@dimc\pst@cntg
    \global\pst@dimg\pst@dimb
    \global\pst@dimh\pst@dimc
  \endgroup}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\pst@getsinandcos}
% "\pst@getsinandcos" normalizes the angle to be in the first quadrant, sets
% "\pst@quadrant" to 0 for the first quadrant, 1 for the second, 2 for the
% third, and 3 for the fourth, invokes "\pst@sinandcos", and sets "\pst@sin"
% to the sine and "\pst@cos" to the cosine.
%    \begin{macrocode}
\def\pst@getsinandcos#1{%
  \pst@dimg=100000sp
  \pst@dimg=#1\pst@dimg
  \pst@dimh=36000000sp
  \pst@cntg=0
  \loop
  \ifnum\pst@dimg<\z@
    \advance\pst@dimg\pst@dimh
  \repeat
  \loop
  \ifnum\pst@dimg>\pst@dimh
    \advance\pst@dimg-\pst@dimh
  \repeat
  \pst@dimh=9000000sp
  \def\pst@tempg{%
    \ifnum\pst@dimg<\pst@dimh\else
      \advance\pst@dimg-\pst@dimh
      \advance\pst@cntg\@ne
      \ifnum\pst@cntg>\thr@@ \advance\pst@cntg-4 \fi
      \expandafter\pst@tempg
    \fi}%
  \pst@tempg
  \chardef\pst@quadrant\pst@cntg
  \ifdim\pst@dimg=\z@
    \def\pst@sin{0}%
    \def\pst@cos{1}%
  \else
    \pst@sinandcos\pst@dimg
    \pst@dimtonum\pst@dimg\pst@sin
    \pst@dimtonum\pst@dimh\pst@cos
  \fi}
%    \end{macrocode}
% \end{macro}
%
% \section{Tilting}
%
% \begin{macro}{\pstilt}
%    \begin{macrocode}
\def\pstilt#1{\pst@makebox{\pstilt@{#1}}}
\def\pstilt@#1{%
  \begingroup
    \leavevmode
    \pst@getsinandcos{#1}%
    \hbox{%
      \ifcase\pst@quadrant
        \kern\pst@cos\dp\pst@hbox
        \pst@dima=\pst@cos\ht\pst@hbox
        \ht\pst@hbox=\pst@sin\ht\pst@hbox
        \dp\pst@hbox=\pst@sin\dp\pst@hbox
      \or
        \kern\pst@sin\ht\pst@hbox
        \pst@dima=\pst@sin\dp\pst@hbox
        \ht\pst@hbox=\pst@cos\ht\pst@hbox
        \dp\pst@hbox=\pst@cos\dp\pst@hbox
      \or
        \kern\pst@cos\ht\pst@hbox
        \pst@dima=\pst@sin\dp\pst@hbox
        \pst@dimg=\pst@sin\ht\pst@hbox
        \ht\pst@hbox=\pst@sin\dp\pst@hbox
        \dp\pst@hbox=\pst@dimg
      \or
        \kern\pst@sin\dp\pst@hbox
        \pst@dima=\pst@sin\ht\pst@hbox
        \pst@dimg=\pst@cos\ht\pst@hbox
        \ht\pst@hbox=\pst@cos\dp\pst@hbox
        \dp\pst@hbox=\pst@dimg
      \fi
      \pst@Verb{%
        { [ 1 0
            \pst@cos\space \ifnum\pst@quadrant>\@ne neg \fi
            \pst@sin\space
            \ifnum\pst@quadrant>\z@\ifnum\pst@quadrant<\thr@@ neg \fi\fi
            \ifodd\pst@quadrant exch \fi
            0 0
          ] concat
        } \tx@TMChange}%
      \box\pst@hbox
      \pst@Verb{\tx@TMRestore}%
      \kern\pst@dima}%
  \endgroup}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\psTilt}
%    \begin{macrocode}
\def\psTilt#1{\pst@makebox{\psTilt@{#1}}}
\def\psTilt@#1{%
  \begingroup
    \leavevmode
    \pst@getsinandcos{#1}%
    \hbox{%
      \ifodd\pst@quadrant
        \pst@@divide{\dp\pst@hbox}{\pst@cos\p@}%
        \ifnum\pst@quadrant=\thr@@\kern\else\pst@dima=\fi\pst@sin\pst@dimg
        \pst@@divide{\ht\pst@hbox}{\pst@cos\p@}%
        \ifnum\pst@quadrant=\@ne\kern\else\pst@dima=\fi\pst@sin\pst@dimg
      \else
        \ifdim\pst@sin\p@=\z@
          \@pstrickserr{\string\psTilt\space angle cannot be 0 or 180}\@ehpa
          \def\pst@sin{.7071}%
          \def\pst@cos{.7071}%
        \fi
        \pst@@divide{\dp\pst@hbox}{\pst@sin\p@}%
        \ifnum\pst@quadrant=\z@\kern\else\pst@dima=\fi\pst@cos\pst@dimg
        \pst@@divide{\ht\pst@hbox}{\pst@sin\p@}%
        \ifnum\pst@quadrant=\tw@\kern\else\pst@dima=\fi\pst@cos\pst@dimg
      \fi
      \ifnum\pst@quadrant>\@ne
        \pst@dimg=\ht\pst@hbox
        \ht\pst@hbox=\dp\pst@hbox
        \dp\pst@hbox=\pst@dimg
      \fi
      \pst@Verb{%
        { [ 1 0
            \pst@cos\space \pst@sin\space
            \ifodd\pst@quadrant exch \fi
            \tx@Div
            \ifnum\pst@quadrant>\z@\ifnum\pst@quadrant<\thr@@ neg \fi\fi
            \ifnum\pst@quadrant>\@ne -1 \else 1 \fi
            0 0
          ] concat
        } \tx@TMChange}%
      \box\pst@hbox
      \pst@Verb{\tx@TMRestore}%
      \kern\pst@dima}%
  \endgroup}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\psset@Tshadowsize,\psTshadowsize}
%    \begin{macrocode}
\def\psset@Tshadowsize#1{\pst@checknum{#1}\psTshadowsize}
\psset@Tshadowsize{1}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\psset@Tshadowangle,\psk@Tshadowangle}
%    \begin{macrocode}
\def\psset@Tshadowangle#1{\pst@getangle{#1}\psk@Tshadowangle}
\psset@Tshadowangle{60}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\psset@Tshadowcolor,\psTshadowcolor}
%    \begin{macrocode}
\def\psset@Tshadowcolor#1{\pst@getcolor{#1}\psTshadowcolor}
\psset@Tshadowcolor{lightgray}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\psshadow}
%    \begin{macrocode}
\def\psshadow{\def\pst@par{}\pst@object{psshadow}}
\def\psshadow@i{\pst@makebox{\psshadow@ii}}
\def\psshadow@ii{%
  \begingroup
    \use@par
    \leavevmode
    \pst@getsinandcos{\psk@Tshadowangle}%
    \hbox{%
      \lower\dp\pst@hbox\hbox{%
        \pst@Verb{%
          { [ 1 0
              \pst@cos\space \psTshadowsize mul
              \ifnum\pst@quadrant>\@ne neg \fi
              \pst@sin\space \psTshadowsize mul
              \ifnum\pst@quadrant>\z@\ifnum\pst@quadrant<\thr@@ neg \fi\fi
              \ifodd\pst@quadrant exch \fi
              0 0
            ] concat
          } \tx@TMChange}}%
      \hbox to\z@{{\@nameuse{\psTshadowcolor}\copy\pst@hbox\hss}}%
      \pst@Verb{\tx@TMRestore}%
      \box\pst@hbox}%
  \endgroup}
%    \end{macrocode}
% \end{macro}

\catcode`\@=\TheAtCode\relax

\endinput
%%
%% END pst-3d.tex

pst-node.tex
%% BEGIN pst-node.tex
%%
%% Nodes with PSTricks 97.
%% See the betadoc documentation for usage. 
%% This uses the header file `pst-node.pro'.
%%
\def\fileversion{97 patch 9}
\def\filedate{1999/04/14}
%%
%% COPYRIGHT 1993, 1994, 1999 by Timothy Van Zandt, tvz@nwu.edu.
%%
%% This program can be redistributed and/or modified under the terms
%% of the LaTeX Project Public License Distributed from CTAN
%% archives in directory macros/latex/base/lppl.txt.
%%
\message{ v\fileversion, \filedate}
\csname PSTnodesLoaded\endcsname
\let\PSTnodesLoaded\endinput
\ifx\PSTricksLoaded\endinput\else\input pstricks.tex\fi\relax
\edef\TheAtCode{\the\catcode`\@}
\catcode`\@=11
\pstheader{pst-node.pro}
\def\pst@nodedict{tx@NodeDict begin }
\def\pst@zapspace#1 #2{%
#1%
\ifx#2\@empty\else\expandafter\pst@zapspace\fi
#2}
\def\pst@getnode#1#2{%
\pst@expandafter\pst@@getnode{#1},,\@nil#2}
\def\pst@@getnode#1,#2,#3\@nil#4{%
\ifx\@empty#3\@empty
\edef#4{/N@\pst@zapspace#1 \@empty\space}%
\else
\pst@cntg=#1\relax
\pst@cnth=#2\relax
\edef#4{/N@M-\ifnum\psmatrixcnt=\z@ 1\else\the\psmatrixcnt\fi
-\the\pst@cntg-\the\pst@cnth\space}%
\fi}
\def\tx@NewNode{NewNode }
\def\pst@newnode#1#2#3#4{%
\leavevmode
\pst@getnode{#1}\pst@thenode
\pst@Verb{%
\pst@nodedict
{#3}
\ifx\psk@name\relax false \else \psk@name true \fi
\pst@thenode
#2
{#4}
\tx@NewNode
end}%
\global\let\psk@name\relax
\pstree@nodehook
\global\let\pstree@nodehook\relax}
\let\pstree@nodehook\relax
\newif\ifnodealign
\def\psset@nodealign#1{\@nameuse{nodealign#1}}
\psset@nodealign{false}
\def\pst@nodealign{%
\pst@dimg=\ht\pst@hbox
\advance\pst@dimg-\dp\pst@hbox
\divide\pst@dimg2
\lower\pst@dimg}
\def\tx@InitPnode{InitPnode }
\def\pnode{\@ifnextchar({\pnode@}{\pnode@(0,0)}}
\def\pnode@(#1)#2{%
\pst@@getcoor{#1}%
\pst@newnode{#2}{10}{\pst@coor}{\tx@InitPnode}%
\ignorespaces}
\def\tx@InitCnode{InitCnode }
\def\cnode{\pst@object{cnode}}
\def\cnode@i{\@ifnextchar({\cnode@ii}{\cnode@ii(0,0)}}
\def\cnode@ii(#1)#2#3{%
\leavevmode
\hbox{%
\use@par
\pst@@getcoor{#1}%
\pssetlength\pst@dimc{#2}%
\pst@dimg=\psk@dimen\pslinewidth
\advance\pst@dimc-\pst@dimg
\advance\pst@dimc.5\pslinewidth
\ifnodealign
\kern\pst@dimc
\vrule width\z@ height \pst@dimc depth \pst@dimc
\fi
\pscircle@do(#1){#2}%
\pst@newnode{#3}{11}{\pst@coor \pst@number\pst@dimc}{\tx@InitCnode}%
% DG/SR modification begin - Jul. 30, 1997 - Patch 2
%\ifnodealign \kern\pst@dimc\egroup \fi}%
\ifnodealign\kern\pst@dimc\fi}%
% DG/SR modification end
\ignorespaces}
\def\Cnode{\pst@object{Cnode}}
\def\Cnode@i{\@ifnextchar({\Cnode@ii}{\Cnode@ii(0,0)}}
\def\Cnode@ii(#1)#2{\cnode@ii(#1){\psk@radius}{#2}}%
\def\cnodeput{\pst@object{cnodeput}}
\def\cnodeput@i{\@ifnextchar({\cnodeput@iii}{\cnodeput@ii}}
\def\cnodeput@ii#1{%
\addto@par{rot={#1}}%
\@ifnextchar({\cnodeput@iii}{\cnodeput@iii(\z@,\z@)}}
\def\cnodeput@iii(#1)#2{%
\pst@killglue
\@fixedradiusfalse
\def\pst@nodehook{\cnodeput@iv{#2}}%
\pst@makebox{\cput@v{#1}}}
\def\cnodeput@iv#1{%
\pst@newnode{#1}{11}{\pscirclebox@iv \pst@number\pslinewidth add}%
{\tx@InitCnode}%
\global\let\pst@nodehook\relax}
\def\Cnodeput{\pst@object{Cnodeput}}
\def\Cnodeput@i{\@ifnextchar({\Cnodeput@iii}{\Cnodeput@ii}}
\def\Cnodeput@ii#1{%
\addto@par{rot={#1}}%
\@ifnextchar({\Cnodeput@iii}{\Cnodeput@iii(\z@,\z@)}}
\def\Cnodeput@iii(#1)#2{%
\pst@killglue
\@fixedradiustrue
\def\pst@nodehook{\Cnodeput@iv{#2}}%
\pst@makebox{\cput@iv{#1}}}
\def\Cnodeput@iv#1{%
\pst@newnode{#1}{11}{%
\pst@number{\wd\pst@hbox} 2 div \pst@number\pst@dima % x y
\pst@number\pst@dimb \pst@number\pslinewidth \psk@dimen .5 sub mul sub }% r
{\tx@InitCnode}%
\global\let\pst@nodehook\relax}
\def\circlenode{\pst@object{circlenode}}
\def\circlenode@i#1{\pst@makebox{\circlenode@ii{#1}}}
\def\circlenode@ii#1{%
\begingroup
\pst@useboxpar
\setbox\pst@hbox=\hbox{%
\cnodeput@iv{#1}%
\pscirclebox@iii
\box\pst@hbox}%
\ifnodealign \psboxseptrue \fi
\ifpsboxsep \pscirclebox@sep \fi
\leavevmode
\ifnodealign\pst@nodealign\fi
\box\pst@hbox
\endgroup}
\def\Circlenode{\pst@object{Circlenode}}
\def\Circlenode@i#1{\pst@makebox{\Circlenode@ii{#1}}}
\def\Circlenode@ii#1{%
\begingroup
\pst@useboxpar
\pst@dima=\ht\pst@hbox
\advance\pst@dima\dp\pst@hbox
\divide\pst@dima\tw@
\pssetlength\pst@dimb\psk@radius
\setbox\pst@hbox=\hbox{%
\Cnodeput@iv{#1}%
\pscircle(.5\wd\pst@hbox,\pst@dima){\pst@dimb}%
\box\pst@hbox}%
\ifnodealign \psboxseptrue \fi
\ifpsboxsep \psCirclebox@sep \fi
\leavevmode
\ifnodealign\pst@nodealign\fi
\box\pst@hbox
\endgroup}
\def\tx@GetRnodePos{GetRnodePos }
\def\tx@InitRnode{InitRnode }
\def\rnode{\@ifnextchar[{\rnode@i}{\def\pst@par{}\rnode@ii}}
\def\rnode@i[#1]{\def\pst@par{ref=#1}\rnode@ii}
\def\rnode@ii#1{\pst@makebox{\rnode@iii\rnode@iv{#1}}}
\def\rnode@iii#1#2{%
% DG modification begin - Jan. 1997
\leavevmode
% DG modification end
\begingroup
% DG/SR modification begin - Apr. 28, 1998 - Patch 6
\pst@useboxpar
% DG/SR modification end
#1%
\if@star\pst@starbox\fi
\ifnodealign\lower\pst@dimb\fi
\hbox{%
\pst@newnode{#2}{16}{%
\pst@number{\ht\pst@hbox}%
\pst@number{\dp\pst@hbox}%
\pst@number{\wd\pst@hbox}%
\pst@number\pst@dima
\pst@number\pst@dimb}%
{\tx@InitRnode}%
\box\pst@hbox}%
\endgroup}
\def\rnode@iv{%
\pst@dima=\psk@xref\wd\pst@hbox
\ifx\psk@yref\relax
\pst@dimb=\z@
\else
\pst@dimb=\ht\pst@hbox
\advance\pst@dimb\dp\pst@hbox
\pst@dimb=\psk@yref\pst@dimb
\advance\pst@dimb-\dp\pst@hbox
\fi}
\def\psset@href#1{\pst@checknum{#1}\psk@href}
\psset@href{0}
\def\psset@vref#1{\def\psk@vref{#1}}
\psset@vref{.7ex}
\def\Rnode{\pst@object{Rnode}}
\def\Rnode@i#1{\pst@makebox{\rnode@iii\Rnode@ii{#1}}}
\def\Rnode@ii{%
% DG modification begin - Jan. 1997
%   - \begingroup removed  as it seems to doesn't work any more
%   - \Rnode doesn't process the optional parameter changes
%\begingroup
\use@par
% DG modification end
\pst@dima=\psk@href\wd\pst@hbox
\advance\pst@dima\wd\pst@hbox
\divide\pst@dima 2
\pssetlength\pst@dimb{\psk@vref}}
\def\tx@DiaNodePos{DiaNodePos }
\def\dianode{\pst@object{dianode}}
\def\dianode@i#1{\pst@makebox{\dianode@ii{#1}}}
\def\dianode@ii#1{%
\begingroup
\pst@useboxpar
\psdiabox@iii
\setbox\pst@hbox=\hbox{%
\pst@newnode{#1}{14}{}{%
/X \pst@number\pst@dima def
/Y \pst@number\pst@dimb def
/w \pst@number\pst@dimc 2 mul def
/h \pst@number\pst@dimd 2 mul def
/NodePos { \tx@DiaNodePos } def}%
\box\pst@hbox}%
\ifnodealign\psboxseptrue\fi
\ifpsboxsep\psdiabox@sep\fi
% DG/SR modification begin - Sep. 2, 1997 - Patch 3
\leavevmode
% DG/SR modification end
\ifnodealign\lower\pst@dimb\fi
\box\pst@hbox
\endgroup}
\def\tx@TriNodePos{TriNodePos }
\def\tx@InitTriNode{InitTriNode }
\def\trinode{\pst@object{trinode}}
\def\trinode@i#1{\pst@makebox{\trinode@ii{#1}}}
\def\trinode@ii#1{%
\begingroup
\pst@useboxpar
\pstribox@iii
\setbox\pst@hbox=\hbox{%
\pst@newnode{#1}{14}{}{%
\pst@number\pst@dimc
\pst@number\pst@dimd
\ifodd\psk@trimode
exch
\pst@number\pst@dima
\else
\pst@number\pst@dimb
\fi
\psk@trimode
\pst@number{\wd\pst@hbox}%
\pst@number{\ht\pst@hbox}%
\pst@number{\dp\pst@hbox}%
\tx@InitTriNode}%
\box\pst@hbox}%
\ifnodealign\psboxseptrue\fi
\ifpsboxsep\pstribox@sep\fi
% DG/SR modification begin - Sep. 2, 1997 - Patch 3
\leavevmode
% DG/SR modification end
\ifnodealign\lower\pst@tempa\fi
\box\pst@hbox
\endgroup}
\def\tx@OvalNodePos{OvalNodePos }
\def\ovalnode{\pst@object{ovalnode}}
\def\ovalnode@i#1{\pst@makebox{\ovalnode@ii{#1}}}
\def\ovalnode@ii#1{%
\begingroup
\pst@useboxpar
\psovalbox@iii
\setbox\pst@hbox=\hbox{%
\pst@newnode{#1}{14}{}{%
/X \pst@number\pst@dima def
/Y \pst@number\pst@dimb def
/w \pst@number\pst@dimc def
/h \pst@number\pst@dimd def
/NodePos { \tx@OvalNodePos } def}%
\unhbox\pst@hbox}%
\ifnodealign\psboxseptrue\fi
\ifpsboxsep\psovalbox@sep\fi
% DG/SR modification begin - Sep. 2, 1997 - Patch 3
\leavevmode
% DG/SR modification end
\ifnodealign\lower\pst@dimb\fi
\box\pst@hbox
\endgroup}
\def\dotnode{\pst@object{dotnode}}
\def\dotnode@i{\@ifnextchar({\dotnode@ii}{\dotnode@ii(\z@,\z@)}}
\def\dotnode@ii(#1)#2{%
\leavevmode
\hbox{%
\use@par
\pst@@getcoor{#1}%
\pst@getdotsize
\pstree@nodehook
\ifnodealign
\pst@dima=\pst@dimg
\kern\pst@dima
\vrule width\z@ height \pst@dimh depth \pst@dimh
\fi
\pst@newnode{#2}{14}{}{%
\pst@coor
/Y ED /X ED
/w \pst@number\pst@dimg def
/h \pst@number\pst@dimh def
/NodePos { \tx@OvalNodePos } def}%
\psdot@ii(#1)%
\ifnodealign\kern\pst@dima\fi}%
\ignorespaces}
\def\psset@framesize#1{\pst@expandafter\psset@@framesize{#1} \@nil}
\def\psset@@framesize#1 #2\@nil{%
\pssetlength\pst@dimg{#1}%
\divide\pst@dimg2
\edef\psk@framewidth{\pst@number\pst@dimg}%
\ifx\@empty#2\@empty
\let\psk@frameheight\psk@framewidth
\else
\pssetlength\pst@dimg{#2}%
\divide\pst@dimg2
\edef\psk@frameheight{\pst@number\pst@dimg}%
\fi}
\psset@framesize{10pt}
\def\fnode{\pst@object{fnode}}
\def\fnode@i{\@ifnextchar({\fnode@ii}{\fnode@ii(\z@,\z@)}}
\def\fnode@ii(#1)#2{%
\leavevmode
\pst@killglue
\hbox{%
\use@par
\begin@ClosedObj
\ifnodealign
\kern\psk@framewidth\p@
\vrule width\z@ height \psk@frameheight\p@ depth \psk@frameheight\p@
\edef\pst@coor{0 0 }%
\else
\pst@@getcoor{#1}%
\fi
\pst@newnode{#2}{14}{}{%
\pst@coor
/Y ED /X ED
/d \psk@dimen .5 sub CLW mul neg def
/r \psk@framewidth d add def
/l r neg def
/u \psk@frameheight d add def
/d u neg def
/NodePos { \tx@GetRnodePos } def}%
\addto@pscode{%
/x2 \psk@framewidth CLW \psk@dimen mul sub def
/y2 \psk@frameheight CLW \psk@dimen mul sub def
\pst@coor 2 copy
y2 sub /y1 ED
x2 sub /x1 ED
y2 add /y2 ED
x2 add /x2 ED
\psk@cornersize
1 index 0 eq { pop pop \tx@Rect } { \tx@OvalFrame } ifelse}%
\def\pst@linetype{2}%
\showpointsfalse
\end@ClosedObj
\ifnodealign\kern\psk@framewidth\p@\fi}%
\ignorespaces}
\def\psset@nodesepA#1{%
\pst@getlength{#1}\psk@nodesepA
\def\psk@nodeseptypeA{0 }}
\def\psset@nodesepB#1{%
\pst@getlength{#1}\psk@nodesepB
\def\psk@nodeseptypeB{0 }}
\def\psset@nodesep#1{%
\pst@getlength{#1}\psk@nodesepA
\let\psk@nodesepB\psk@nodesepA
\def\psk@nodeseptypeA{0 }%
\def\psk@nodeseptypeB{0 }}
\psset@nodesep{0pt}
\def\psset@XnodesepA#1{%
\pst@getlength{#1}\psk@nodesepA
\def\psk@nodeseptypeA{1 }}
\def\psset@XnodesepB#1{%
\pst@getlength{#1}\psk@nodesepB
\def\psk@nodeseptypeB{1 }}
\def\psset@Xnodesep#1{%
\pst@getlength{#1}\psk@nodesepA
\let\psk@nodesepB\psk@nodesepA
\def\psk@nodeseptypeA{1 }%
\def\psk@nodeseptypeB{1 }}
\def\psset@YnodesepA#1{%
\pst@getlength{#1}\psk@nodesepA
\def\psk@nodeseptypeA{2 }}
\def\psset@YnodesepB#1{%
\pst@getlength{#1}\psk@nodesepB
\def\psk@nodeseptypeB{2 }}
\def\psset@Ynodesep#1{%
\pst@getlength{#1}\psk@nodesepA
\let\psk@nodesepB\psk@nodesepA
\def\psk@nodeseptypeA{2 }%
\def\psk@nodeseptypeB{2 }}
\def\psset@armA#1{%
\pst@getlength{#1}\psk@armA
\def\psk@armtypeA{0 }}
\def\psset@armB#1{%
\pst@getlength{#1}\psk@armB
\def\psk@armtypeB{0 }}
\def\psset@arm#1{%
\pst@getlength{#1}\psk@armA
\let\psk@armB\psk@armA
\def\psk@armtypeA{0 }%
\def\psk@armtypeB{0 }}
\psset@arm{10pt}
\def\psset@XarmA#1{%
\pst@getlength{#1}\psk@armA
\def\psk@armtypeA{1 }}
\def\psset@XarmB#1{%
\pst@getlength{#1}\psk@armB
\def\psk@armtypeB{1 }}
\def\psset@Xarm#1{%
\pst@getlength{#1}\psk@armA
\let\psk@armB\psk@armA
\def\psk@armtypeA{1 }%
\def\psk@armtypeB{1 }}
\def\psset@YarmA#1{%
\pst@getlength{#1}\psk@armA
\def\psk@armtypeA{2 }}
\def\psset@YarmB#1{%
\pst@getlength{#1}\psk@armB
\def\psk@armtypeB{2 }}
\def\psset@Yarm#1{%
\pst@getlength{#1}\psk@armA
\let\psk@armB\psk@armA
\def\psk@armtypeA{2 }%
\def\psk@armtypeB{2 }}
\def\psset@offsetA#1{\pst@getlength{#1}\psk@offsetA}
\def\psset@offsetB#1{\pst@getlength{#1}\psk@offsetB}
\def\psset@offset#1{\psset@offsetA{#1}\let\psk@offsetB\psk@offsetA}
\psset@offset{0pt}
\def\psset@angleA#1{\pst@getangle{#1}\psk@angleA}
\def\psset@angleB#1{\pst@getangle{#1}\psk@angleB}%
\def\psset@angle#1{%
\pst@getangle{#1}\psk@angleA
\let\psk@angleB\psk@angleA}
\psset@angle{0}
\def\psset@arcangleA#1{\pst@getangle{#1}\psk@arcangleA}
\def\psset@arcangleB#1{\pst@getangle{#1}\psk@arcangleB}%
\def\psset@arcangle#1{%
\pst@getangle{#1}\psk@arcangleA
\let\psk@arcangleB\psk@arcangleA}
\psset@arcangle{8}
\def\psset@ncurvA#1{\pst@checknum{#1}\psk@ncurvA}
\def\psset@ncurvB#1{\pst@checknum{#1}\psk@ncurvB}%
\def\psset@ncurv#1{\psset@ncurvA{#1}\let\psk@ncurvB\psk@ncurvA}
\psset@ncurv{.67}
\def\tx@GetCenter{GetCenter }
\def\tx@XYPos{XYPos }
\def\tx@GetEdge{GetEdge }
\def\tx@AddOffset{AddOffset }
\def\tx@GetEdgeA{GetEdgeA }
\def\tx@GetEdgeB{GetEdgeB }
\def\tx@GetArmA{GetArmA }
\def\tx@GetArmB{GetArmB }
\def\check@arrow#1#2{%
\check@@arrow#2-\@nil
\if@pst
\addto@par{arrows=#2}%
\def\next{#1}%
\else
\def\next{#1{#2}}%
\fi
\next}
\def\check@@arrow#1-#2\@nil{%
\ifx\@nil#2\@nil\@pstfalse\else\@psttrue\fi}
\def\tx@InitNC{InitNC }
\def\nc@object#1#2#3#4#5{%
\csname begin@#1Obj\endcsname
\showpointsfalse
\pst@getnode{#2}\pst@tempa
\pst@getnode{#3}\pst@tempb
\gdef\npos@default{#4 }%
\addto@pscode{%
/NCLW CLW def
\pst@nodedict
\psk@offsetA
\psk@offsetB neg
\psk@nodesepA
\psk@nodesepB
\psk@nodeseptypeA
\psk@nodeseptypeB
\pst@tempa
\pst@tempb
\tx@InitNC { #5 } if
end}%
\def\use@pscode{%
\pst@Verb{gsave \tx@STV newpath \pst@code\space grestore}%
\gdef\pst@code{}}%
\csname end@#1Obj\endcsname
\pst@shortput}
\def\npos@default{.5 }
\def\pc@object#1{%
\@ifnextchar({\pc@@object#1}{\pst@getarrows{\pc@@object#1}}}
\def\pc@@object#1(#2)(#3){%
\pnode(#2){@@A}\pnode(#3){@@B}%
#1{@@A}{@@B}}
\def\tx@LPutLine{LPutLine }
\def\tx@LPutLines{LPutLines }
\def\tx@BezierMidpoint{BezierMidpoint }
\def\tx@HPosBegin{HPosBegin }
\def\tx@HPosEnd{HPosEnd }
\def\tx@HPutLine{HPutLine }
\def\tx@HPutLines{HPutLines }
\def\tx@VPosBegin{VPosBegin }
\def\tx@VPosEnd{VPosEnd }
\def\tx@VPutLine{VPutLine }
\def\tx@VPutLines{VPutLines }
\def\tx@HPutCurve{HPutCurve }
\def\tx@NCCoor{NCCoor }
\def\tx@NCLine{NCLine }
\def\ncline{\pst@object{ncline}}
\def\ncline@i{\check@arrow{\ncline@ii}}
\def\ncline@ii#1#2{\nc@object{Open}{#1}{#2}{.5}{\tx@NCLine}}
\def\pcline{\pst@object{pcline}}
\def\pcline@i{\pc@object\ncline@ii}
\def\ncLine{\pst@object{ncLine}}
\def\ncLine@i{\check@arrow{\ncLine@ii}}
\def\ncLine@ii#1#2{\nc@object{Open}{#1}{#2}{.5}%
% DG/SR modification begin - Apr. 14, 1999 - Patch 9
%{\tx@NCLine /LPutPos { xB xA yB yA \tx@LPutLine } def}}
{\tx@NCLine /LPutPos { xB yB xA yA \tx@LPutLine } def}}
% DG/SR modification end
\def\tx@NCLines{NCLines }
\def\nclines{\pst@object{nclines}}
\def\nclines@i{\check@arrow\nclines@ii}
\def\nclines@ii#1#2{%
\begingroup
\use@par
\def\pst@aftercoors{\nclines@iii{#1}{#2}}%
\def\pst@coors{}%
\pst@@getcoors}
\def\nclines@iii#1#2{%
\nc@object{Open}{#1}{#2}{.5}{%
tx@Dict begin \psline@iii pop end
mark \pst@coors \tx@NCLines}%
\endgroup
\ignorespaces}
\def\tx@NCCurve{NCCurve }
\def\nccurve{\pst@object{nccurve}}
\def\nccurve@i{\check@arrow{\nccurve@ii}}
\def\nccurve@ii#1#2{\nc@object{Open}{#1}{#2}{.5}{%
/AngleA \psk@angleA\space def /AngleB \psk@angleB\space def
\psk@ncurvB\space \psk@ncurvA\space
\tx@NCCurve}}
\def\pccurve{\pst@object{pccurve}}
\def\pccurve@i{\pc@object\nccurve@ii}
\def\ncarc{\pst@object{ncarc}}
\def\ncarc@i{\check@arrow{\ncarc@ii}}
\def\ncarc@ii#1#2{\nc@object{Open}{#1}{#2}{.5}{%
yB yA sub xB xA sub \tx@Atan dup
\psk@arcangleA\space add /AngleA ED
\psk@arcangleB\space sub 180 add /AngleB ED
\psk@ncurvB\space \psk@ncurvA\space
\tx@NCCurve}}
\def\pcarc{\pst@object{pcarc}}
\def\pcarc@i{\pc@object\ncarc@ii}
\def\tx@NCAngles{NCAngles }
\def\ncangles{\pst@object{ncangles}}
\def\ncangles@i{\check@arrow{\ncangles@ii}}
\def\ncangles@ii#1#2{%
\nc@object{Open}{#1}{#2}{1.5}{\ncangles@iii \tx@NCAngles}}
\def\ncangles@iii{%
tx@Dict begin \psline@iii pop end
/AngleA \psk@angleA def
/AngleB \psk@angleB def
/ArmA \psk@armA def
/ArmB \psk@armB def
/ArmTypeA \psk@armtypeA def
/ArmTypeB \psk@armtypeB def }
\def\pcangles{\pst@object{pcangles}}
\def\pcangles@i{\pc@object\ncangles@ii}
\def\tx@NCAngle{NCAngle }
\def\ncangle{\pst@object{ncangle}}
\def\ncangle@i{\check@arrow{\ncangle@ii}}
\def\ncangle@ii#1#2{%
\nc@object{Open}{#1}{#2}{1.5}{\ncangles@iii \tx@NCAngle}}
\def\pcangle{\pst@object{pcangle}}
\def\pcangle@i{\pc@object\ncangle@ii}
\def\tx@NCBar{NCBar }
\def\ncbar{\pst@object{ncbar}}
\def\ncbar@i{\check@arrow{\ncbar@ii}}
\def\ncbar@ii#1#2{\nc@object{Open}{#1}{#2}{1.5}{%
\ncangles@iii /AngleB \psk@angleA def \tx@NCBar}}
\def\pcbar{\pst@object{pcbar}}
\def\pcbar@i{\pc@object\ncbar@ii}
\def\tx@NCDiag{NCDiag }
\def\ncdiag{\pst@object{ncdiag}}
\def\ncdiag@i{\check@arrow{\ncdiag@ii}}
\def\ncdiag@ii#1#2{%
\nc@object{Open}{#1}{#2}{1.5}{\ncangles@iii \tx@NCDiag}}
\def\pcdiag{\pst@object{pcdiag}}
\def\pcdiag@i{\pc@object\ncdiag@ii}
\def\tx@NCDiagg{NCDiagg }
\def\ncdiagg{\pst@object{ncdiagg}}
\def\ncdiagg@i{\check@arrow{\ncdiagg@ii}}
\def\ncdiagg@ii#1#2{%
\nc@object{Open}{#1}{#2}{.5}{\ncangles@iii \tx@NCDiagg}}
\def\pcdiagg{\pst@object{pcdiagg}}
\def\pcdiagg@i{\pc@object\ncdiagg@ii}
\def\tx@NCLoop{NCLoop }
\def\psset@loopsize#1{\pst@getlength{#1}\psk@loopsize}
\psset@loopsize{1cm}
\def\ncloop{\pst@object{ncloop}}
\def\ncloop@i{\check@arrow{\ncloop@ii}}
\def\ncloop@ii#1#2{%
\nc@object{Open}{#1}{#2}{2.5}%
{\ncangles@iii /loopsize \psk@loopsize def \tx@NCLoop}}
\def\pcloop{\pst@object{pcloop}}
\def\pcloop@i{\pc@object\ncloop@ii}
\def\tx@NCCircle{NCCircle }
\def\nccircle{\pst@object{nccircle}}
\def\nccircle@i{\check@arrow{\nccircle@ii}}
\def\nccircle@ii#1#2{%
\pssetlength\pst@dima{#2}%
\nc@object{Open}{#1}{#1}{.5}{%
/AngleA \psk@angleA def
/r \pst@number\pst@dima def
\tx@NCCircle \psarc@v end}}
\def\tx@NCBox{NCBox }
\def\ncbox{\pst@object{ncbox}}
\def\ncbox@i{\check@arrow{\ncbox@ii}}
\def\ncbox@ii#1#2{%
\def\pst@linetype{2}%
\nc@object{Closed}{#1}{#2}{.5}{%
tx@Dict begin \psline@iii pop end
\psk@boxheight \psk@boxdepth
\tx@NCBox}}
\def\pcbox{\pst@object{pcbox}}
\def\pcbox@i{\pc@object\ncbox@ii}
\def\tx@NCArcBox{NCArcBox }
\def\psset@boxheight#1{\pst@getlength{#1}\psk@boxheight}
\def\psset@boxdepth#1{\pst@getlength{#1}\psk@boxdepth}
\def\psset@boxsize#1{%
\psset@boxheight{#1}%
\let\psk@boxdepth\psk@boxheight}
\psset@boxsize{.4cm}
\def\ncarcbox{\pst@object{ncarcbox}}
\def\ncarcbox@i{\check@arrow{\ncarcbox@ii}}
\def\ncarcbox@ii#1#2{%
\def\pst@linetype{1}%
\nc@object{Closed}{#1}{#2}{.5}{%
\psk@arcangleA \psk@boxheight \psk@boxdepth \pst@number\pslinearc
\tx@NCArcBox}}
\def\pcarcbox{\pst@object{pcarcbox}}
\def\pcarcbox@i{\pc@object\ncarcbox@ii}
\def\tx@Tfan{Tfan }
% Changed according pst-beta.bug December 3, 1993
% nrot=:<angle> does not work when : is active.
\begingroup
\catcode`\:=13
\gdef\pst@activerot{\def:{\string:}}
\endgroup
\def\psset@nrot#1{%
\begingroup
\pst@activerot
\pst@expandafter{\@ifnextchar:{\psset@@nrot}{\psset@@rot}}{#1}\@nil
\global\let\pst@tempg\psk@rot
\endgroup
\let\psk@nrot\pst@tempg}
\def\psset@@nrot:#1\@nil{%
\psset@@rot#1\@nil
\edef\psk@rot{NAngle \ifx\psk@rot\@empty\else\psk@rot add \fi}}
\psset@nrot{0}
\def\tx@LPutCoor{LPutCoor }
\def\tx@LPut{LPut }
\def\psset@npos#1{%
\def\pst@tempa{#1}%
\ifx\pst@tempa\@empty
\def\psk@npos{\npos@default}%
\else
\pst@checknum{#1}\psk@npos
\fi}
\psset@npos{}
\def\ncput{\pst@object{ncput}}
\def\ncput@i{\pst@killglue\pst@makebox{\ncput@ii}}
\def\ncput@ii{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\pst@makesmall\pst@hbox
\pst@rotate\psk@nrot\pst@hbox
\ncput@iii
\endgroup
\pst@shortput}
\def\ncput@iii{%
\leavevmode
\hbox{%
\pst@Verb{%
\pst@nodedict
/t \psk@npos def
\tx@LPut
end
\tx@PutBegin}%
\box\pst@hbox
\pst@Verb{\tx@PutEnd}}}
\def\naput{\pst@object{naput}}
\def\naput@i{\pst@killglue\pst@makebox{\naput@ii{NAngle 90 add}}}
\def\naput@ii#1{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\def\psk@refangle{#1 }%
\let\psk@rot\psk@nrot
\uput@vii
{exch pop add a \tx@PtoC h1 add exch w1 add exch }%
{tx@Dict /NCLW known { NCLW add } if }%
\ncput@iii
\endgroup
\pst@shortput}
\def\nbput{\pst@object{nbput}}
\def\nbput@i{\pst@killglue\pst@makebox{\naput@ii{NAngle 90 sub}}}
\def\psset@tpos#1{%
\pst@checknum{#1}\psk@tpos
\ifdim\psk@tpos \p@<\z@
\def\psk@tpos{.5}%
% DG/SR modification begin - Sep. 23, 1998 - Patch 7
%\@pstrickserr{Bad `tpos' value: `#1'. Must be 0<tpos<1}\@epha
\@pstrickserr{Bad `tpos' value: `#1'. Must be 0<tpos<1}\@ehpa
% DG/SR modification end
\else
\ifdim\psk@tpos \p@>\p@
\def\psk@tpos{.5}%
% DG/SR modification begin - Sep. 23, 1998 - Patch 7
%\@pstrickserr{Bad `tpos' value: `#1'. Must be 0<tpos<1}\@epha
\@pstrickserr{Bad `tpos' value: `#1'. Must be 0<tpos<1}\@ehpa
% DG/SR modification end
\fi
\fi}
\psset@tpos{.5}
\def\tvput{\pst@object{tvput}}
\def\tvput@i{\pst@makebox{\psput@tput{H}{1}}}
\def\tlput{\pst@object{tlput}}
\def\tlput@i{\pst@makebox{\psput@tput{H}{true}}}
\def\trput{\pst@object{trput}}
\def\trput@i{\pst@makebox{\psput@tput{H}{false}}}
\def\thput{\pst@object{thput}}
\def\thput@i{\pst@makebox{\psput@tput{V}{1}}}
\def\taput{\pst@object{taput}}
\def\taput@i{\pst@makebox{\psput@tput{V}{true}}}
\def\tbput{\pst@object{tbput}}
\def\tbput@i{\pst@makebox{\psput@tput{V}{false}}}
\def\tx@HPutAdjust{HPutAdjust }
\def\tx@VPutAdjust{VPutAdjust }
\def\psput@tput#1#2{%
\begingroup
\use@par
\pst@tputmakesmall
\leavevmode
\hbox{%
\pst@Verb{%
\pst@nodedict
/t \psk@tpos \pst@tposflip def
tx@NodeDict /HPutPos known
{ #1PutPos }
{ CP /Y ED /X ED /NAngle 0 def /NCLW 0 def }
ifelse
/Sin NAngle sin def
/Cos NAngle cos def
/s \pst@number\pslabelsep NCLW add def
/l \pst@number\pst@dima def
/r \pst@number\pst@dimb def
/h \pst@number\pst@dimc def
/d \pst@number\pst@dimd def
% DG/SR modification begin - Sep. 26, 1997 - Patch 4
%\ifnum1=0#2\else
\ifnum1=0#2 \else
% DG/SR modification end
/flag #2 def
\csname tx@#1PutAdjust\endcsname
\fi
\tx@LPutCoor
end
\tx@PutBegin}%
\box\pst@hbox
\pst@Verb{\tx@PutEnd}}%
\endgroup
\pst@shortput}
\def\pst@tposflip{}
\def\pst@tputmakesmall{%
\pst@dima=\wd\pst@hbox
\divide\pst@dima 2
\pst@dimg=\psk@href\pst@dimg
\pst@dimb\pst@dima
\advance\pst@dima\pst@dimg % leftsize
\advance\pst@dimb-\pst@dimg % rightsize
\pst@dimd=\psk@vref\relax
\pst@dimc=\ht\pst@hbox
\advance\pst@dimc-\pst@dimd % height
\advance\pst@dimd\dp\pst@hbox % depth
\setbox\pst@hbox=\hbox to\z@{%
\kern-\pst@dima\vbox to\z@{\vss\box\pst@hbox\vskip-\pst@dimd}\hss}}
\def\MakeShortNab#1#2{%
  \def\pst@shortput@nab{%
    \def\pst@tempg{\next}%
    \ifx#1\next
      \let\pst@tempg\naput
    \else
      \ifx#2\next
        \let\pst@tempg\nbput
      \else
        \ifx\@sptoken\next
          \let\pst@tempg\pst@shortput
        \fi
      \fi
    \fi
    \pst@tempg}}
\MakeShortNab{^}{_}
\def\MakeShortTablr#1#2#3#4{%
  \def\pst@shortput@tablr{%
    \def\pst@tempg{\next}%
    \ifx#1\next
      \let\pst@tempg\taput
    \else
      \ifx#2\next
        \let\pst@tempg\tbput
      \else
        \ifx#3\next
          \let\pst@tempg\tlput
        \else
          \ifx#4\next
            \let\pst@tempg\trput
          \else
            \ifx\@sptoken\next
              \let\pst@tempg\pst@shortput
            \fi
          \fi
        \fi
      \fi
    \fi
    \pst@tempg}}
\MakeShortTablr{^}{_}{<}{>}
\def\MakeShortTab#1#2{%
  \def\pst@shortput@tab{%
    \def\pst@tempg{\next}%
    \ifx#1\next
      \def\pst@tempg{%
        \@nameuse{%
          t\ifodd\psk@treemode\ifpstreeflip b\else a\fi
          \else\ifpstreeflip r\else l\fi\fi put}}%
    \else
      \ifx#2\next
        \def\pst@tempg{%
          \@nameuse{%
            t\ifodd\psk@treemode\ifpstreeflip a\else b\fi
            \else\ifpstreeflip l\else r\fi\fi put}}%
      \else
        \ifx\@sptoken\next
          \let\pst@tempg\pst@shortput
        \fi
      \fi
    \fi
    \pst@tempg}}
\MakeShortTab{^}{_}
\def\psset@shortput#1{%
\def\pst@tempg{#1}%
\ifx\pst@tempg\@none
\let\pst@shortput\ignorespaces
\else
\@ifundefined{pst@shortput@#1}%
{\@pstrickserr{Bad short put: `#1'}\@ehpa}%
{\edef\pst@shortput{\noexpand\afterassignment\expandafter\noexpand
\csname pst@shortput@#1\endcsname\noexpand\let\noexpand\next}}%
\fi}
\psset@shortput{none}
\def\lput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\lput@i}{\lput@ii}}}
\def\lput@i[#1]{\addto@par{ref=#1}\lput@ii}
\def\lput@ii{\@ifnextchar({\lput@iv}{\lput@iii}}
\def\lput@iii#1{\addto@par{nrot=#1}\@ifnextchar({\lput@iv}{\ncput@i}}
\def\lput@iv(#1){\addto@par{npos=#1}\ncput@i}
\def\mput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\mput@i}{\ncput@i}}}
\def\mput@i[#1]{\addto@par{ref=#1}\ncput@i}
\def\Lput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\Lput@ii}{\Lput@i}}}
\def\Lput@i#1{\addto@par{labelsep=#1}\Lput@ii}
\def\Lput@ii[#1]{\addto@par{ref={#1}}\@ifnextchar({\Lput@iv}{\Lput@iii}}
\def\Lput@iii#1{\addto@par{nrot={#1}}\@ifnextchar({\Lput@iv}{\Lput@v}}
\def\Lput@iv(#1){\addto@par{npos=#1}\Lput@v}
\def\Lput@v{\pst@killglue\pst@makebox{\Lput@vi}}
\def\Lput@vi{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\Rput@vi
\pst@makesmall\pst@hbox
\pst@rotate\psk@nrot\pst@hbox
\ncput@iii
\endgroup
\pst@shortput}
\def\Mput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\Mput@ii}{\Mput@i}}}
\def\Mput@i#1{\addto@par{labelsep=#1}\Mput@ii}
\def\Mput@ii[#1]{\addto@par{ref={#1}}\Lput@v}
\def\aput@#1{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\aput@i#1}{\aput@ii#1}}}
\def\aput@i#1[#2]{\addto@par{labelsep=#2}\aput@ii#1}
\def\aput@ii#1{\@ifnextchar({\aput@iv#1}{\aput@iii#1}}
\def\aput@iii#1#2{\addto@par{nrot=#2}\@ifnextchar({\aput@iv#1}{#1}}
\def\aput@iv#1(#2){\addto@par{npos=#2}#1}
\def\aput{\aput@\naput@i}
\def\bput{\aput@\nbput@i}
\def\Aput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\Aput@i}{\naput@i}}}
\def\Aput@i[#1]{\addto@par{labelsep=#1}\naput@i}
\def\Bput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\Bput@i}{\nbput@i}}}
\def\Bput@i[#1]{\addto@par{labelsep=#1}\nbput@i}
\def\node@coor#1;#2\@nil{%
\pst@getnode{#1}\pst@tempg
\edef\pst@coor{%
\pst@nodedict
tx@NodeDict \pst@tempg known
{ \pst@tempg load \tx@GetCenter }
{ 0 0 }
ifelse
end }}
\def\Node@coor[#1]#2;#3\@nil{%
\begingroup
\psset{#1}%
\@ifnextchar\bgroup{\Node@@@coor}{\Node@@coor}#2\@nil
\endgroup
\let\pst@coor\pst@tempg}
\def\Node@@coor#1\@nil{%
\pst@getnode{#1}\pst@tempg
\xdef\pst@tempg{%
\pst@nodedict
tx@NodeDict \pst@tempg known
{ \psk@nodesepA \psk@angleA
\pst@tempg load \psk@nodeseptypeA \tx@GetEdge
\psk@offsetA \psk@angleA \tx@AddOffset
\pst@tempg load \tx@GetCenter
3 -1 roll add 3 1 roll add exch }
{ CP }
ifelse
end }}%
\def\Node@@@coor#1{%
\pst@@getcoor{#1}%
\def\psk@angleA{%
\pst@tempg load \tx@GetCenter \pst@coor
3 -1 roll sub 3 1 roll sub neg \tx@Atan}%
\Node@@coor}
\def\nput{\pst@object{nput}}
\def\nput@i#1#2{\pst@killglue\pst@makebox{\nput@ii{#1}{#2}}}
\def\nput@ii#1#2{%
\begingroup
\use@par
\psset@refangle{#1}%
\let\psk@angleA\psk@refangle
\edef\psk@nodesepA{\pst@number\pslabelsep}%
\def\psk@nodeseptypeA{0 }%
\pslabelsep\z@
\uput@vi
\Node@@coor#2\@nil
\let\pst@coor\pst@tempg
\leavevmode
\psput@special\pst@hbox
\endgroup
\ignorespaces}
\newcount\psrow
\newcount\pscol
\newcount\psmatrixcnt
\newskip\psrowsep
\newskip\pscolsep
\def\psset@colsep#1{\pssetlength\pscolsep{#1}}
\def\psset@rowsep#1{\pssetlength\psrowsep{#1}}
\psset@colsep{1.5cm}
\psset@rowsep{1.5cm}
\newif\ifpsmatrix
% DG/SR modification begin - Nov. 27, 1998 - Patch 8
%\let\mscount\@multicnt
\ifx\mscount\@undefined\let\mscount\@multicnt\fi
% DG/SR modification end
\def\psmatrix{%
  \begingroup
{\ifnum0=`}\fi % Don't want to expand any &.
\@ifnextchar[{\psmatrix@i}{\ifnum0=`{\fi}{}\psmatrix@ii}}
\def\psmatrix@i[#1]{%
\ifnum0=`{\fi}{}%
\psset{#1}%
\psmatrix@ii}
\def\psmatrix@ii{%
\KillGlue
\edef\psm@beginmath{%
\ifmmode$\m@th\ifinner\textstyle\else\displaystyle\fi\fi}%
\edef\psm@endmath{\ifmmode$\fi}%
\let\\\psm@cr
\advance\psmatrixcnt 1
\def\psm@thenode{M-\the\psmatrixcnt-\the\psrow-\the\pscol}%
\tabskip\z@
\psrow1
\pscol\z@
\psset@shortput{tablr}%
\leavevmode
\vbox\bgroup\halign\bgroup&%
\begingroup
\global\advance\pscol 1
\csname psrowhook\romannumeral\psrow\endcsname
\csname pscolhook\romannumeral\pscol\endcsname
\psm@beginnode##\psm@endnode\endgroup
\cr}
\def\endpsmatrix{%
\crcr\egroup\unskip\egroup
\endgroup}
\def\psm@cr{{\ifnum0=`}\fi\@ifnextchar[{\psm@@cr}{\psm@@@cr{}}}
\def\psm@@cr[#1]{\psm@@@cr{\vskip#1\relax}}
\def\psm@@@cr#1{%
\ifnum0=`{\fi}{}\cr
\noalign{%
\global\advance\psrow 1
\global\pscol\z@
\vskip\psrowsep
#1}}
\def\psm@beginnode{%
\@ifnextchar\psm@endnode
{\let\psm@endnode@i\relax\setbox\pst@hbox=\hbox{}}%
{\pst@object{psm@beginnode}}}
\def\psm@beginnode@i{%
\setbox\pst@hbox=\hbox\bgroup
\psm@beginmath
\begingroup
\ignorespaces}
\def\psm@endnode@i{%
\unskip
\endgroup
\psm@endmath
\egroup
\use@par
\@psttrue}
\def\psm@endnode{%
\@pstfalse
\psm@endnode@i
\ifnum\pscol>1 \hskip\pscolsep \fi
\psk@mnodesize
\hfil
\nodealigntrue
\if@pst
\csname mnode@\psk@mnode\endcsname
\else
\csname mnode@\psk@emnode\endcsname
\fi
\psk@mcol
\psk@@mnodesize}
\def\psspan#1{\mscount#1\relax\loop\ifnum\mscount>\@ne \sp@n\repeat}
\def\psset@name#1{\pst@getnode{#1}\psk@name}
\let\psk@name\relax
\def\psset@mcol#1{%
\ifx r#1\relax
\let\psk@mcol\relax
\else
\ifx l#1\relax
\let\psk@mcol\hfill
\else
\let\psk@mcol\hfil
\fi
\fi}
\psset@mcol{c}
\def\psset@mnodesize#1{%
\pssetlength\pst@dimg{#1}%
\ifdim\pst@dimg<\z@
\let\psk@mnodesize\relax
\let\psk@@mnodesize\relax
\else
\edef\psk@mnodesize{\noexpand\hbox to\number\pst@dimg sp\noexpand\bgroup}%
\let\psk@@mnodesize\egroup
\fi}
\psset@mnodesize{-1pt}
\def\mnode@R{\rnode@iii\Rnode@ii{\psm@thenode}}
\def\mnode@r{\rnode@iii\rnode@iv{\psm@thenode}}
\def\mnode@oval{\ovalnode@ii{\psm@thenode}}
\def\mnode@tri{\trinode@ii{\psm@thenode}}
\def\mnode@dia{\dianode@ii{\psm@thenode}}
\def\mnode@C{{\nodealigntrue\cnode@ii(\z@,\z@){\psk@radius}{\psm@thenode}}}
\def\mnode@f{{\nodealigntrue\fnode@ii(\z@,\z@){\psm@thenode}}}
\def\mnode@circle{\circlenode@ii{\psm@thenode}}
\def\mnode@p{\pnode(\z@,\z@){\psm@thenode}}
% DG/SR modification begin - Jul. 22, 1997 - Patch 1
\def\mnode@dot{\dotnode@ii(\z@,\z@){\psm@thenode}}
% DG/SR modification end
\def\mnode@none{\box\pst@hbox}
\def\psset@mnode#1{%
\@ifundefined{mnode@#1}%
{\@pstrickserr{\string\psmatrix\space node `#1' not defined.}\@ehpa}%
{\edef\psk@mnode{#1}}}
\def\psset@emnode#1{%
\@ifundefined{mnode@#1}%
{\@pstrickserr{\string\psmatrix\space node `#1' not defined.}\@ehpa}%
{\edef\psk@emnode{#1}}}
\psset@mnode{R}
\psset@emnode{none}
%%%% FROM pst-coil.tex
\def\nccoil{\pst@object{nccoil}}
\def\nccoil@i{\check@arrow{\nccoil@ii}}
\def\nccoil@ii#1#2{\nc@object{Open}{#1}{#2}{.5}{%
\tx@NCCoor
tx@Dict begin
% DG/SR modification begin - Mar. 19, 1998 - Patch 5
4 2 roll
% DG/SR modification end
\psk@coilwidth \pscoilheight
\psk@coilarmA \psk@coilarmB
\psk@coilaspect \psk@coilinc
\pst@coildict \tx@Coil end
end}}
\def\nczigzag{\pst@object{nczigzag}}
\def\nczigzag@i{\check@arrow{\nczigzag@ii}}
\def\nczigzag@ii#1#2{\nc@object{Open}{#1}{#2}{.5}{%
\tx@NCCoor
tx@Dict begin
% DG/SR modification begin - Mar. 19, 1998 - Patch 5
4 2 roll
% DG/SR modification end
\pscoilheight
\psk@coilwidth
\psk@coilarmA
\psk@coilarmB
\pst@coildict \tx@ZigZag end
\psline@iii
\tx@Line
end}}
\catcode`\@=\TheAtCode\relax
\endinput
%%
%% END pst-node.tex

pst-text.tex
%% BEGIN pst-text.tex
%%
%% Placing text on a path with PSTricks 97.
%% See the PSTricks User's Guide for description.
%% See tp-test.tex for sample input and tp-test.ps for sample output.
%% This uses the header file `pst-text.pro'.
%%
\def\fileversion{97}
\def\filedate{1997/03/25}
%%
%% COPYRIGHT 1993, 1994, 1999 by Timothy Van Zandt, tvz@nwu.edu.
%%
%% This program can be redistributed and/or modified under the terms
%% of the LaTeX Project Public License Distributed from CTAN
%% archives in directory macros/latex/base/lppl.txt.
%%
\message{ v\fileversion, \filedate}

\csname PSTextPathLoaded\endcsname
\let\PSTextPathLoaded\endinput

\ifx\PSTricksLoaded\endinput\else
  \def\next{\input pstricks.tex}\expandafter\next
\fi

\edef\TheAtCode{\the\catcode`\@}
\catcode`\@=11

\pstheader{pst-text.pro}

\def\pstextpath{\@ifnextchar[{\pstextpath@}{\pstextpath@[l]}}
\def\pstextpath@[#1]{%
  \@ifnextchar({\pstextpath@@[#1]}{\pstextpath@@[#1](0,\TPoffset)}}
\def\pstextpath@@[#1](#2)#3{\pst@makebox{\pstextpath@@@[#1](#2){#3}}}
\def\pstextpath@@@[#1](#2,#3)#4{%
  \pst@killglue
  \begingroup
    \ifx c#1\relax
      \def\pst@tempa{.5}%
    \else
      \ifx r#1\relax
        \def\pst@tempa{1}%
      \else
        \def\pst@tempa{0}%
      \fi
    \fi
    \def\use@pscode{%
      \pst@Verb{%
        /mtrxc CM def
        \tx@STV
        CP translate
        newpath
        \pst@code\space
        mtrxc setmatrix
        0 setgray}%
      \gdef\pst@code{}}%
    \def\psclip#1{\pst@misplaced\psclip}%
    \let\endpsclip\relax
    \def\@multips(##1)(##2)##3##4{\pst@misplaced\multips}%
    \def\nc@object##1##2##3##4{\pst@misplaced{node connection}}%
    \def\PSTtoEPS@i##1##2{\pst@misplaced\PSTtoEPS}%
    \pssetlength\pst@dima{#2}%
    \pssetlength\pst@dimb{#3}%
    \setbox\pst@hbox\hbox{%
      \hbox to\z@{%
        \kern -\wd\pst@hbox
        % BoxWidth = CurrX - Hoffset.
        \pstVerb{tx@TextPathDict begin
          currentpoint pop /Hoffset exch def end}%
        \kern\pst@dima
        % XOffset = Voffset - Hoffset (extra horizontal skip)
        \pstVerb{tx@TextPathDict begin
          currentpoint pop /Voffset exch def end}%
        \hss
        \pstVerb{%
          /tx@TextPathSavedShow /show load def
          \pst@dict \tx@PathLength end
          dup 0 gt
          { tx@TextPathDict begin \pst@tempa\space InitTextPath end
            /show { tx@TextPathDict begin TextPathShow end } def
          }
          { pop }
          ifelse}}%
      \raise\pst@dimb\box\pst@hbox
      \pstVerb{%
        currentpoint newpath moveto
        /show /tx@TextPathSavedShow load def}}%
    \wd\pst@hbox=\z@ \dp\pst@hbox=\z@ \ht\pst@hbox=\z@
    \leavevmode
    \hbox{{#4}\box\pst@hbox}%
  \endgroup\ignorespaces}
\def\TPoffset{-.7ex}

\catcode`\@=\TheAtCode\relax

\endinput
%%
%% END pst-text.tex

pstricks.tex
%% BEGIN: pstricks.tex
%%
%% PostScript macros for Generic TeX: main input file for PSTricks 97.
%% See the PSTricks User's Guide for description.
%% This uses the header file `pstricks.pro'.
%%
\def\fileversion{97 patch 10}
\def\filedate{1999/03/24}
%%
%% COPYRIGHT 1993, 1994, 1999 by Timothy Van Zandt, tvz@nwu.edu.
%%
%% This program can be redistributed and/or modified under the terms
%% of the LaTeX Project Public License Distributed from CTAN
%% archives in directory macros/latex/base/lppl.txt.
%%
\csname PSTricksLoaded\endcsname
\let\PSTricksLoaded\endinput
\edef\PstAtCode{\the\catcode`\@}
\catcode`\@=11\relax
\expandafter\ifx\csname @latexerr\endcsname\relax
\long\def\@ifundefined#1#2#3{\expandafter\ifx\csname
#1\endcsname\relax#2\else#3\fi}
\def\@namedef#1{\expandafter\def\csname #1\endcsname}
\def\@nameuse#1{\csname #1\endcsname}
\def\@eha{%
Your command was ignored.^^J
Type \space I <command> <return> \space to replace
it with another command,^^J
or \space <return> \space to continue without it.}
\def\@spaces{\space\space\space\space}
\def\typeout#1{\immediate\write\@unused{#1}}
\alloc@7\write\chardef\sixt@@n\@unused
\def\@empty{}
\def\@gobble#1{}
\def\@nnil{\@nil}
\def\@ifnextchar#1#2#3{%
\let\@tempe#1\def\@tempa{#2}\def\@tempb{#3}\futurelet\@tempc\@ifnch}
\def\@ifnch{%
\ifx\@tempc\@sptoken
\let\@tempd\@xifnch
\else
\ifx\@tempc\@tempe \let\@tempd\@tempa \else \let\@tempd\@tempb \fi
\fi
\@tempd}
\begingroup
\def\:{\global\let\@sptoken= } \:
\def\:{\@xifnch} \expandafter\gdef\: {\futurelet\@tempc\@ifnch}
\endgroup
\fi
\typeout{`PSTricks' v\fileversion\space\space <\filedate> (tvz)}
\def\@pstrickserr#1#2{%
\begingroup
\newlinechar`\^^J
\edef\pst@tempc{#2}%
\expandafter\errhelp\expandafter{\pst@tempc}%
\typeout{%
PSTricks error. \space See User's Guide for further information.^^J
\@spaces\@spaces\@spaces\@spaces
Type \space H <return> \space for immediate help.}%
\errmessage{#1}%
\endgroup}
\def\@ehpa{%
Your command was ignored. Default value substituted.^^J
Type \space <return> \space to procede.}
\def\@ehpb{%
Your command was ignored. Will recover best I can.^^J
Type \space <return> \space to procede.}
\def\@ehpc{%
You better fix this before proceding.^^J
See the PSTricks User's Guide or ask your system administrator for help.^^J
Type \space X <return> \space to quit.}
\def\pst@misplaced#1{\@pstrickserr{Misplaced \string#1 command}\@ehpb}
\newdimen\pst@dima
\newdimen\pst@dimb
\newdimen\pst@dimc
\newdimen\pst@dimd
\newdimen\pst@dimg
\newdimen\pst@dimh
\newbox\pst@hbox
\newbox\pst@boxg
\newcount\pst@cnta
\newcount\pst@cntb
\newcount\pst@cntc
\newcount\pst@cntd
\newcount\pst@cntg
\newcount\pst@cnth
\newif\if@pst
\newtoks\pst@toks
\newif\if@star
\def\pst@ifstar#1{%
\@ifnextchar*{\@startrue\def\next*{#1}\next}{\@starfalse#1}}
\def\pst@expandafter#1#2{%
\def\next{#1}%
\edef\@tempa{#2}%
\ifx\@tempa\@empty
\@pstrickserr{Unexpected empty argument!}\@ehpb
\def\@tempa{\@empty}%
\fi
\expandafter\next\@tempa}
\def\pst@dimtonum#1#2{\edef#2{\pst@@dimtonum#1}}
\def\pst@@dimtonum#1{\expandafter\pst@@@dimtonum\the#1}
{\catcode`\p=12 \catcode`\t=12 \global\@namedef{pst@@@dimtonum}#1pt{#1}}
\def\pst@pyth#1#2#3{%
\ifdim#1>#2\pst@@pyth#1#2#3\else\pst@@pyth#2#1#3\fi}
\def\pst@@pyth#1#2#3{%
\ifdim4#1>9#2%
#3=#1\advance#3 .2122#2%
\else
#3=.8384#1\advance#3 .5758#2%
\fi}
\def\pst@divide#1#2#3{%
\pst@@divide{#1}{#2}%
\pst@dimtonum\pst@dimg{#3}}
\def\pst@@divide#1#2{%
\pst@dimg=#1\relax
\pst@dimh=#2\relax
\pst@cntg=\pst@dimh
\pst@cnth=67108863
\pst@@@divide\pst@@@divide\pst@@@divide\pst@@@divide
\divide\pst@dimg\pst@cntg}
\def\pst@@@divide{%
\ifnum
\ifnum\pst@dimg<\z@-\fi\pst@dimg<\pst@cnth
\multiply\pst@dimg\sixt@@n
\else
\divide\pst@cntg\sixt@@n
\fi}
\def\pst@configerr#1{%
\@pstrickserr{\string#1 not defined in pstricks.con}\@ehpc}
% % \begin{macrocode}
\def\pstVerb#1{\pst@configerr\pstVerb}
\def\pstverb#1{\pst@configerr\pstverb}
\def\pstverbscale{\pst@configerr\pstverbscale}
\def\pstrotate{\pst@configerr\pstrotate}
\def\pstheader#1{\pst@configerr\pstheader}
\def\pstdriver{\pst@configerr\pstdriver}
\@ifundefined{pstcustomize}%
{\def\pstcustomize{\endinput\let\pstcustomize\relax}}{}
\input pstricks.con
\newif\ifPSTricks
\PSTrickstrue
\def\PSTricksOff{%
\def\pstheader##1{}%
\def\pstverb##1{}%
\def\pstVerb##1{}%
\PSTricksfalse}
\@ifundefined{pst@def}{\def\pst@def#1<#2>{\@namedef{tx@#1}{#2 }}}{}
\@ifundefined{pst@ATH}{\def\pst@ATH<#1>{}}{}
\pstheader{pstricks.pro}
\def\pst@dict{tx@Dict begin }
\def\pst@theheaders{pstricks.pro}
\def\pst@Verb#1{\pstVerb{\pst@dict #1 end}}
\def\tx@Atan{Atan }
\def\tx@Div{Div }
\def\tx@NET{NET }
\def\tx@Pyth{Pyth }
\def\tx@PtoC{PtoC }
\def\tx@PathLength@{PathLength@ }
\def\tx@PathLength{PathLength }
\pst@dimg=\pstunit\relax
\ifdim\pst@dimg=1bp
\def\pst@stp{.996264 dup scale}
\else
\edef\pst@stp{1 \pst@@dimtonum\pst@dimg\space div dup scale}
\fi
\def\tx@STP{STP }
\def\tx@STV{STV }
\def\pst@number#1{\pst@@dimtonum#1\space}
\def\pst@checknum#1#2{%
\edef\next{#1}%
\ifx\next\@empty
\let\pst@num\z@
\else
\expandafter\pst@@checknum\next..\@nil
\fi
\ifnum\pst@num=\z@
\@pstrickserr{Bad number: `#1'. 0 substituted.}\@ehpa
\def#2{0 }%
\else
\edef#2{\ifnum\pst@num=\tw@-\fi\the\pst@cntg.%
\expandafter\@gobble\the\pst@cnth\space}%
\fi}
\def\pst@@checknum{%
\@ifnextchar-%
{\let\pst@num\tw@\expandafter\pst@@@checknum\@gobble}%
{\let\pst@num\@ne\pst@@@checknum}}
\def\pst@@@checknum#1.#2.#3\@nil{%
\afterassignment\pst@@@@checknum\pst@cntg=0#1\relax\@nil
\afterassignment\pst@@@@checknum\pst@cnth=1#2\relax\@nil}
\def\pst@@@@checknum#1\relax\@nil{%
\ifx\@nil#1\@nil\else\let\pst@num\z@\fi}
\def\pst@getnumii#1 #2 #3\@nil{%
\pst@checknum{#1}\pst@tempg
\pst@checknum{#2}\pst@temph}
\def\pst@getnumiii#1 #2 #3 #4\@nil{%
\pst@checknum{#1}\pst@tempg
\pst@checknum{#2}\pst@temph
\pst@checknum{#3}\pst@tempi}
\def\pst@getnumiv#1 #2 #3 #4 #5\@nil{%
\pst@checknum{#1}\pst@tempg
\pst@checknum{#2}\pst@temph
\pst@checknum{#3}\pst@tempi
\pst@checknum{#4}\pst@tempj}
\def\pst@getdimnum#1 #2 #3\@nil{%
\pssetlength\pst@dimg{#1}%
\pst@checknum{#2}\pst@tempg}
% DG/SR modification begin - Jan. 7, 1998 - Patch 9
% Missing from pstricks.bug 0.93
%\def\pst@getscale#1#2{%
%\pst@expandafter\pst@getnumii{#1 #1} {} {} {}\@nil
%\@psttrue
%\ifdim\pst@tempg\p@=\z@
%\@pstrickserr{Bad scaling argument `#1'}\@ehpa
%\def\pst@tempg{1 }%
%\@pstfalse
%\fi
%\ifdim\pst@temph\p@=\z@
%\if@pst\@pstrickserr{Bad scaling argument `#1'}\@ehpa\fi
%\def\pst@temph{1 }%
%\fi
%\edef#2{\pst@tempg\space \pst@temph\space scale }%
%\ifdim\pst@tempg\p@=\p@ \ifdim\pst@temph\p@=\p@
%\def#2{}%
%\fi\fi}
\def\pst@getscale#1#2{%
\edef\pst@tempg{#1}%
\ifx\pst@tempg\@none
\def#2{}%
\else
\pst@expandafter\pst@getnumii{#1 #1} {} {} {}\@nil
\ifdim\pst@tempg\p@=\z@
\@pstrickserr{Bad scaling argument `#1'}\@ehpa
\def#2{}%
\else
\ifdim\pst@temph\p@=\z@
\@pstrickserr{Bad scaling argument `#1'}\@ehpa
\def#2{}%
\else
\edef#2{\pst@tempg\space \pst@temph\space scale }%
\fi
\fi
\fi}
% DG/SR modification end
\def\pst@getint#1#2{%
\pst@cntg=#1\relax
\edef#2{\the\pst@cntg\space}}
\begingroup
\catcode`\{=12
\catcode`\}=12
\catcode`\[=1
\catcode`\]=2
\gdef\pslbrace[{ ]
\gdef\psrbrace[} ]
\endgroup
\def\@newcolor#1#2{%
\expandafter\edef\csname #1\endcsname{\noexpand\pst@color{#2}}%
\expandafter\edef\csname color@#1\endcsname{#2}%
\ignorespaces}
\def\pst@color#1{%
\def\pst@currentcolor{#1}\pstVerb{#1}\aftergroup\pst@endcolor}
\def\pst@endcolor{\pstVerb{\pst@currentcolor}}
\def\pst@currentcolor{0 setgray}
\def\altcolormode{%
\def\pst@color##1{%
\pstVerb{gsave ##1}\aftergroup\pst@endcolor}%
\def\pst@endcolor{\pstVerb{\pst@grestore}}}
\def\pst@grestore{%
currentpoint
matrix currentmatrix
currentfont
grestore
setfont
setmatrix
moveto}
\def\pst@usecolor#1{\csname color@#1\endcsname\space}
\def\newgray#1#2{%
\pst@checknum{#2}\pst@tempg
\@newcolor{#1}{\pst@tempg setgray}}
\def\newrgbcolor#1#2{%
\pst@expandafter\pst@getnumiii{#2} {} {} {} {}\@nil
\@newcolor{#1}{\pst@tempg \pst@temph \pst@tempi setrgbcolor}}
\def\newhsbcolor#1#2{%
\pst@expandafter\pst@getnumiii{#2} {} {} {} {}\@nil
\@newcolor{#1}{\pst@tempg \pst@temph \pst@tempi sethsbcolor}}
\def\newcmykcolor#1#2{%
\pst@expandafter\pst@getnumiv{#2} {} {} {} {} {}\@nil
\@newcolor{#1}{\pst@tempg \pst@temph \pst@tempi \pst@tempj setcmykcolor}}
\newgray{black}{0}
\newgray{darkgray}{.25}
\newgray{gray}{.5}
\newgray{lightgray}{.75}
\newgray{white}{1}
\newrgbcolor{red}{1 0 0}
\newrgbcolor{green}{0 1 0}
\newrgbcolor{blue}{0 0 1}
\newrgbcolor{yellow}{1 1 0}
\newrgbcolor{cyan}{0 1 1}
\newrgbcolor{magenta}{1 0 1}
\def\psset#1{\@psset#1,\@nil\ignorespaces}
\def\@psset#1,{%
\@@psset#1==\@nil
\@ifnextchar\@nil{\@gobble}{\@psset}}
\def\@@psset#1=#2=#3\@nil{%
\@ifundefined{psset@#1}%
{\@pstrickserr{Graphics parameter `#1' not defined.}\@ehpa}%
{\@nameuse{psset@#1}{#2}}}%
\def\psset@style#1{%
\@ifundefined{pscs@#1}%
{\@pstrickserr{Custom style `#1' undefined}\@ehpa}%
{\@nameuse{pscs@#1}}}
\def\newpsstyle#1#2{\@namedef{pscs@#1}{\psset{#2}}}
\def\@none{none}
\def\pst@getcolor#1#2{%
\@ifundefined{color@#1}%
{\@pstrickserr{Color `#1' not defined}\@eha}%
{\edef#2{#1}}}
\newdimen\psunit \psunit 1cm
\newdimen\psxunit \psxunit 1cm
\newdimen\psyunit \psyunit 1cm
\let\psrunit\psunit
\def\pstunit@off{\let\@psunit\ignorespaces\ignorespaces}
\def\pssetlength#1#2{%
\let\@psunit\psunit
\afterassignment\pstunit@off
#1 #2\@psunit}
\def\psaddtolength#1#2{%
\let\@psunit\psunit
\afterassignment\pstunit@off
\advance#1 #2\@psunit}
\def\pssetxlength#1#2{%
\let\@psunit\psxunit
\afterassignment\pstunit@off
#1 #2\@psunit}
\def\pssetylength#1#2{%
\let\@psunit\psyunit
\afterassignment\pstunit@off
#1 #2\@psunit}
\def\psset@unit#1{%
\pssetlength\psunit{#1}%
\psxunit=\psunit
\psyunit=\psunit}
\def\psset@runit#1{\pssetlength\psrunit{#1}}
\def\psset@xunit#1{\pssetxlength\psxunit{#1}}
\def\psset@yunit#1{\pssetylength\psyunit{#1}}
\def\pst@getlength#1#2{%
\pssetlength\pst@dimg{#1}%
\edef#2{\pst@number\pst@dimg}}
\def\pst@@getlength#1#2{%
\pssetlength\pst@dimg{#1}%
\edef#2{\number\pst@dimg sp}}
\def\pst@getcoor#1#2{\pst@@getcoor{#1}\let#2\pst@coor}
\def\pst@coor{0 0 }
\def\pst@getcoors#1#2{%
\def\pst@aftercoors{\addto@pscode{#1 \pst@coors }#2}%
\def\pst@coors{}%
\pst@@getcoors}
\def\pst@@getcoors(#1){%
\pst@@getcoor{#1}%
\edef\pst@coors{\pst@coor\pst@coors}%
\@ifnextchar({\pst@@getcoors}{\pst@aftercoors}}
\def\pst@getangle#1#2{\pst@@getangle{#1}\let#2\pst@angle}
\def\pst@angle{0 }
\def\cartesian@coor#1,#2,#3\@nil{%
\pssetxlength\pst@dimg{#1}%
\pssetylength\pst@dimh{#2}%
\edef\pst@coor{\pst@number\pst@dimg \pst@number\pst@dimh}}
\def\NormalCoor{%
\def\pst@@getcoor##1{\pst@expandafter\cartesian@coor{##1},\relax,\@nil}%
\def\pst@@getangle##1{%
\pst@checknum{##1}\pst@angle
\edef\pst@angle{\pst@angle \pst@angleunit}}%
\def\psput@##1{\pst@@getcoor{##1}\leavevmode\psput@cartesian}}
\NormalCoor
\def\degrees{\@ifnextchar[{\@degrees}{\def\pst@angleunit{}}}
\def\@degrees[#1]{%
\pst@checknum{#1}\pst@tempg
\edef\pst@angleunit{360 \pst@tempg div mul }%
\ignorespaces}
\def\radians{\def\pst@angleunit{57.2956 mul }}
\def\pst@angleunit{}
\def\SpecialCoor{%
\def\pst@@getcoor##1{%
\begingroup
\pst@activecoor
\xdef\pst@tempg{##1}%
\endgroup
\expandafter\special@coor\pst@tempg||\@nil}%
\def\pst@@getangle##1{%
\begingroup
\pst@activecoor
\xdef\pst@tempg{##1}%
\endgroup
\expandafter\special@angle\pst@tempg\@empty)\@nil}%
\def\psput@##1{\pst@@getcoor{##1}\leavevmode\psput@special}}
\begingroup
\catcode`\|=13
\catcode`\;=13
\catcode`\!=13
\gdef\pst@activecoor{%
\def|{\string|}%
\def;{\string;}%
\def!{\string!}}
\endgroup
\def\special@coor#1|#2|#3\@nil{%
\ifx#3|\relax
\mixed@coor{#1}{#2}%
\else
\special@@coor#1;;\@nil
\fi}
\def\special@@coor#1{%
\ifcat#1a\relax
\def\next{\node@coor#1}%
\else
\ifx#1[\relax
\def\next{\Node@coor[}%
\else
\ifx#1!\relax
\def\next{\raw@coor}%
\else
\def\next{\special@@@coor#1}%
\fi
\fi
\fi
\next}
\def\special@@@coor#1;#2;#3\@nil{%
\ifx#3;\relax
\polar@coor{#1}{#2}%
\else
\cartesian@coor#1,\relax,\@nil
\fi}
\def\mixed@coor#1#2{%
\begingroup
% DG/SR modification begin - Oct. 27, 1997 - Patch 6
%\specialcoor@ii#1;;\@nil
%\let\pst@tempa\pst@coor
%\specialcoor@ii#2;;\@nil
\special@@coor#1;;\@nil
\let\pst@tempa\pst@coor
\special@@coor#2;;\@nil
% DG/SR modification end
\xdef\pst@tempg{\pst@tempa pop \pst@coor exch pop }%
\endgroup
\let\pst@coor\pst@tempg}
\def\polar@coor#1#2{%
\pssetlength\pst@dimg{#1}%
\pst@@getangle{#2}%
\edef\pst@coor{\pst@number\pst@dimg \pst@angle \tx@PtoC}}
\def\raw@coor#1;#2\@nil{%
\edef\pst@coor{%
#1 \pst@number\psyunit mul exch \pst@number\psxunit mul exch }}
\def\node@coor#1\@nil{%
\@pstrickserr{You must load `pst-node.tex' to use node coordinates.}\@ehps
\def\pst@coor{0 0 }}
\def\Node@coor{\node@coor}
\def\special@angle#1#2)#3\@nil{%
\ifx!#1\relax
\edef\pst@angle{#2 \pst@angleunit}%
\else
\ifx(#1\relax
\pst@@getcoor{#2}%
\edef\pst@angle{\pst@coor exch \tx@Atan}%
\else
\pst@checknum{#1#2}\pst@angle
\edef\pst@angle{\pst@angle \pst@angleunit}%
\fi
\fi}
\def\Cartesian{%
\def\cartesian@coor##1,##2,##3\@nil{%
\pssetxlength\pst@dimg{##1}%
\pssetylength\pst@dimh{##2}%
\edef\pst@coor{\pst@number\pst@dimg \pst@number\pst@dimh}}%
\@ifnextchar({\Cartesian@}{}}
\def\Cartesian@(#1,#2){%
\pssetxlength\psxunit{#1}%
\pssetylength\psyunit{#2}%
\ignorespaces}
\def\Polar{%
\def\psput@cartesian{\psput@special}%
\def\cartesian@coor##1,##2,##3\@nil{\polar@coor{##1}{##2}}}%
\def\psset@origin#1{%
\pst@@getcoor{#1}%
\edef\psk@origin{\pst@coor \tx@NET }}
\def\psk@origin{}
\newif\ifswapaxes
\def\psset@swapaxes#1{%
\@nameuse{@pst#1}%
\if@pst
\def\psk@swapaxes{-90 rotate -1 1 scale }%
\else
\def\psk@swapaxes{}%
\fi}
\psset@swapaxes{false}
\newif\ifshowpoints
\def\psset@showpoints#1{\@nameuse{showpoints#1}}
\psset@showpoints{false}
\let\pst@setrepeatarrowsflag\relax
\def\psset@border#1{%
\pst@getlength{#1}\psk@border
\pst@setrepeatarrowsflag}
\psset@border{0pt}
\def\psset@bordercolor#1{\pst@getcolor{#1}\psbordercolor}
\psset@bordercolor{white}
\newif\ifpsdoubleline
\def\psset@doubleline#1{%
\@nameuse{psdoubleline#1}%
\pst@setrepeatarrowsflag}
\psset@doubleline{false}
\def\psset@doublesep#1{\def\psdoublesep{#1}}
\psset@doublesep{1.25\pslinewidth}
\def\psset@doublecolor#1{\pst@getcolor{#1}\psdoublecolor}
\psset@doublecolor{white}
\newif\ifpsshadow
\def\psset@shadow#1{%
\@nameuse{psshadow#1}%
\pst@setrepeatarrowsflag}
\psset@shadow{false}
\def\psset@shadowsize#1{\pst@getlength{#1}\psk@shadowsize}
\psset@shadowsize{3pt}
\def\psset@shadowangle#1{\pst@getangle{#1}\psk@shadowangle}
\psset@shadowangle{-45}
\def\psset@shadowcolor#1{\pst@getcolor{#1}\psshadowcolor}
\psset@shadowcolor{darkgray}
\def\pst@repeatarrowsflag{\z@}
\def\pst@setrepeatarrowsflag{%
\edef\pst@repeatarrowsflag{%
\ifdim\psk@border\p@>\z@ 1\else\ifpsdoubleline 1\else
\ifpsshadow 1\else \z@\fi\fi\fi}}
\def\psls@none{}
\newdimen\pslinewidth
\def\psset@linewidth#1{\pssetlength\pslinewidth{#1}}
\psset@linewidth{.8pt}
\def\psset@linecolor#1{\pst@getcolor{#1}\pslinecolor}
\psset@linecolor{black}
\def\psls@solid{0 setlinecap stroke }
\def\pst@missing{%
\z@
\@pstrickserr{Missing number or dimension. 0 substituted}\@ehpa}
\def\psset@dash#1{%
\pst@expandafter\psset@@dash{#1} {\pst@missing} {\pst@missing} {}\@nil
\edef\psk@dash{\pst@number\pst@dimg \pst@number\pst@dimh}}
\def\psset@@dash#1 #2 #3\@nil{%
\pssetlength\pst@dimg{#1}%
\pssetlength\pst@dimh{#2}}
\psset@dash{5pt 3pt}
\newif\ifpsdashadjust
\def\psset@dashadjust#1{\@nameuse{psdashadjust#1}}
\psset@dashadjust{true}
\def\psls@dashed{%
\ifpsdashadjust
\psk@dash \pst@linetype\space \tx@DashLine
\else
[ \psk@dash ] 0 setdash stroke
\fi}
\def\tx@DashLine{DashLine }
\def\psset@dotsep#1{\pst@getlength{#1}\psk@dotsep}
\psset@dotsep{3pt}
\def\psls@dotted{%
\ifpsdashadjust
\psk@dotsep \pst@linetype\space \tx@DotLine
\else
[ 0 \psk@dotsep CLW add ] 0 setdash 1 setlinecap stroke
\fi}
\def\tx@DotLine{DotLine }
\def\psset@linestyle#1{%
\@ifundefined{psls@#1}%
{\@pstrickserr{Line style `#1' not defined}\@eha}%
{\edef\pslinestyle{#1}}}
\psset@linestyle{solid}
\def\psfs@none{}
\def\psset@fillcolor#1{\pst@getcolor{#1}\psfillcolor}
\psset@fillcolor{white}
\def\psfs@solid{\pst@fill{\pst@usecolor\psfillcolor fill}}
\def\psset@hatchwidth#1{\pst@getlength{#1}\psk@hatchwidth}
\psset@hatchwidth{.8pt}
\def\psset@hatchsep#1{\pst@getlength{#1}\psk@hatchsep}
\psset@hatchsep{4pt}
\def\psset@hatchcolor#1{\pst@getcolor{#1}\pshatchcolor}
\psset@hatchcolor{black}
\def\psset@hatchangle#1{\pst@getangle{#1}\psk@hatchangle}
\psset@hatchangle{45}
\def\pst@linefill{%
\psk@hatchangle rotate
\psk@hatchwidth SLW
\pst@usecolor\pshatchcolor
\psk@hatchsep \tx@LineFill}
\def\psfs@vlines{\pst@fill\pst@linefill}
\@namedef{psfs@vlines*}{\psfs@solid \psfs@vlines}
\def\psfs@hlines{\pst@fill{90 rotate \pst@linefill}}
\@namedef{psfs@hlines*}{\psfs@solid \psfs@hlines}
\def\psfs@crosshatch{\psfs@vlines \psfs@hlines}
\@namedef{psfs@crosshatch*}{\psfs@solid \psfs@vlines \psfs@hlines}
\def\tx@LineFill{LineFill }
\def\psset@fillstyle#1{%
\edef\pst@tempg{#1}\def\pst@temph{none}%
\ifx\pst@tempg\pst@temph
\let\psk@fillstyle\relax
\else
\@ifundefined{psfs@#1}%
{\@pstrickserr{Undefined fill style: `#1'}\@eha}%
{\edef\psk@fillstyle{\expandafter\noexpand\csname psfs@#1\endcsname}}%
\fi}
\def\psset@addfillstyle#1{%
\@ifundefined{psfs@#1}%
{\@pstrickserr{Undefined fill style: `#1'}\@eha}%
{\edef\psk@fillstyle{%
\expandafter\noexpand\psk@fillstyle
\expandafter\noexpand\csname psfs@#1\endcsname}}}
\psset@fillstyle{none}
\def\psset@arrows#1{%
\begingroup
\pst@activearrows
\xdef\pst@tempg{#1}%
\endgroup
\expandafter\psset@@arrows\pst@tempg\@empty-\@empty\@nil
\if@pst\else
\@pstrickserr{Bad arrows specification: #1}\@ehpa
\fi}
\def\psset@@arrows#1-#2\@empty#3\@nil{%
\@psttrue
\def\next##1,#1-##2,##3\@nil{\def\pst@tempg{##2}}%
\expandafter\next\pst@arrowtable,#1-#1,\@nil
\@ifundefined{psas@\pst@tempg}%
{\@pstfalse\def\psk@arrowA{}}%
{\let\psk@arrowA\pst@tempg}%
\@ifundefined{psas@#2}%
{\@pstfalse\def\psk@arrowB{}}%
{\def\psk@arrowB{#2}}}
\def\psk@arrowA{}
\def\psk@arrowB{}
\def\pst@arrowtable{,<->,<<->>,>-<,>>-<<,(-),[-]}
\begingroup
\catcode`\<=13
\catcode`\>=13
\catcode`\|=13
\gdef\pst@activearrows{\def<{\string<}\def>{\string>}\def|{\string|}}
\endgroup
\def\tx@BeginArrow{BeginArrow }
\def\tx@EndArrow{EndArrow }
\def\psset@arrowscale#1{\pst@getscale{#1}\psk@arrowscale}
\psset@arrowscale{1}
\def\psset@arrowsize#1{%
\pst@expandafter\pst@getdimnum{#1} 0 {} {}\@nil
\edef\psk@arrowsize{\pst@number\pst@dimg \pst@tempg}}
\psset@arrowsize{1.5pt 2}
\def\psset@arrowlength#1{\pst@checknum{#1}\psk@arrowlength}
\psset@arrowlength{1.4}
\def\psset@arrowinset#1{\pst@checknum{#1}\psk@arrowinset}%
\psset@arrowinset{.4}
\def\tx@Arrow{Arrow }
\@namedef{psas@>}{%
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\@namedef{psas@>>}{%
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow
0 h T
gsave
newpath
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow
CP
grestore
CP newpath moveto
2 copy
L
stroke
moveto}
\@namedef{psas@<}{%
true \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\@namedef{psas@<<}{%
true \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow
CP newpath moveto 0 a neg L stroke 0 h neg T
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\def\psset@tbarsize#1{%
\pst@expandafter\pst@getdimnum{#1} 0 {} {}\@nil
\edef\psk@tbarsize{\pst@number\pst@dimg \pst@tempg}}
\psset@tbarsize{2pt 5}
\def\tx@Tbar{Tbar }
\@namedef{psas@|}{\psk@tbarsize \tx@Tbar}
\@namedef{psas@|*}{0 CLW -2 div T \psk@tbarsize \tx@Tbar}
\@namedef{psas@>|}{%
\psk@tbarsize \tx@Tbar
0 CLW 2 div T
newpath
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\@namedef{psas@>|*}{%
0 CLW -2 div T
\psk@tbarsize \tx@Tbar
0 CLW 2 div T
newpath
false \psk@arrowinset \psk@arrowlength \psk@arrowsize \tx@Arrow}
\edef\pst@arrowtable{\pst@arrowtable,|<*->|*,|<->|}
\def\psset@bracketlength#1{\pst@checknum{#1}\psk@bracketlength}
\psset@bracketlength{.15}
\def\tx@Bracket{Bracket }
\@namedef{psas@]}{\psk@bracketlength \psk@tbarsize \tx@Bracket}
\def\psset@rbracketlength#1{\pst@checknum{#1}\psk@rbracketlength}
\psset@rbracketlength{.15}
\def\tx@RoundBracket{RoundBracket }
\@namedef{psas@)}{\psk@rbracketlength \psk@tbarsize \tx@RoundBracket}
\def\psas@c{1 \psas@@c}
\def\psas@cc{0 CLW 2 div T 1 \psas@@c}
\def\psas@C{2 \psas@@c}
\def\psas@@c{%
setlinecap
0 0 moveto
0 CLW 2 div L
stroke
0 0 moveto}
\def\psas@{}
\psset@arrows{-}
\def\tx@SD{SD }
\def\tx@EndDot{EndDot }
\def\psas@oo{{\pst@usecolor\psfillcolor true} true \psk@dotsize \tx@EndDot}
\def\psas@o{{\pst@usecolor\psfillcolor true} false \psk@dotsize \tx@EndDot}
\@namedef{psas@**}{{false} true \psk@dotsize \tx@EndDot}
\@namedef{psas@*}{{false} false \psk@dotsize \tx@EndDot}
\def\pst@par{}
\def\addto@par#1{%
\ifx\pst@par\@empty
\def\pst@par{#1}%
\else
\expandafter\def\expandafter\pst@par\expandafter{\pst@par,#1}%
\fi}
\def\addbefore@par#1{%
\ifx\pst@par\@empty
\def\pst@par{#1}%
\else
\toks@{#1}%
\pst@toks\expandafter{\pst@par}%
\edef\pst@par{\the\toks@,\the\pst@toks}%
\fi}
\def\use@par{%
\ifx\pst@par\@empty\else
\expandafter\@psset\pst@par,\@nil
\def\pst@par{}%
\fi}
\def\pst@object#1{%
\pst@ifstar{%
\@ifnextchar[%
{\pst@@object{#1}}%
{\def\pst@par{}\@nameuse{#1@i}}}}
\def\pst@@object#1[#2]{%
\def\pst@par{#2}%
\@ifnextchar+{\@nameuse{#1@i}}{\@nameuse{#1@i}}}
\def\newpsobject#1#2#3{%
\@ifundefined{#2@i}%
{\@pstrickserr{Graphics object `#2' not defined}\@eha}{%
\@namedef{#1}{\pst@object{#1}}%
\@namedef{#1@i}{\addbefore@par{#3}\@nameuse{#2@i}}}%
\ignorespaces}
\def\pst@getarrows#1{\@ifnextchar({#1}{\pst@@getarrows{#1}}}
\def\pst@@getarrows#1#2{\addto@par{arrows=#2}#1}
\def\begin@ClosedObj{%
\leavevmode
\pst@killglue
\begingroup
\use@par
\solid@star
\ifpsdoubleline \pst@setdoublesep \fi
\init@pscode}
\def\end@ClosedObj{%
\ifpsshadow \pst@closedshadow \fi
\ifdim\psk@border\p@>\z@ \pst@addborder \fi
\psk@fillstyle
\pst@stroke
\ifpsdoubleline \pst@doublestroke \fi
\ifshowpoints
% DG modification begin - Mar. 4, 1995
%\addto@pscode{Points aload length 2 div cvi /N ED \psdots@iii}%
\pst@OpenShowPoints
% DG modification end
\fi
\use@pscode
\endgroup
\ignorespaces}
\def\begin@OpenObj{%
\begin@ClosedObj
\let\pst@linetype\pst@arrowtype
\pst@addarrowdef}
\def\begin@AltOpenObj{%
\begin@ClosedObj
\def\pst@repeatarrowsflag{\z@}%
\def\pst@linetype{0}}
\def\end@OpenObj{%
\ifpsshadow \pst@openshadow \fi
\ifdim\psk@border\p@>\z@ \pst@addborder \fi
\psk@fillstyle
\pst@stroke
\ifpsdoubleline \pst@doublestroke \fi
\ifnum\pst@repeatarrowsflag>\z@ \pst@repeatarrows \fi
\ifshowpoints \pst@OpenShowPoints \fi
\use@pscode
\endgroup
\ignorespaces}
\def\begin@SpecialObj{%
\leavevmode
\pst@killglue
\begingroup
\use@par
\init@pscode}
\def\end@SpecialObj{%
\use@pscode
\endgroup
\ignorespaces}
\def\pst@code{}%
\def\init@pscode{%
\addto@pscode{%
\pst@number\pslinewidth SLW
\pst@usecolor\pslinecolor}}
\def\addto@pscode#1{\xdef\pst@code{\pst@code#1\space}}
\def\use@pscode{%
\pstverb{%
\pst@dict
\tx@STP
\pst@newpath
\psk@origin
\psk@swapaxes
\pst@code
end}%
\gdef\pst@code{}}
\def\pst@newpath{newpath }
\def\pst@@killglue{\unskip\ifdim\lastskip>\z@\expandafter\pst@@killglue\fi}
\def\KillGlue{\let\pst@killglue\pst@@killglue}
\def\DontKillGlue{\let\pst@killglue\relax}
\DontKillGlue
\def\solid@star{%
\if@star
\pslinewidth=\z@
\psdoublelinefalse
\def\pslinestyle{none}%
\def\psk@fillstyle{\psfs@solid}%
\let\psfillcolor\pslinecolor
\fi}
\def\pst@setdoublesep{%
\pst@getlength\psdoublesep\psdoublesep
\pslinewidth=2\pslinewidth
\advance\pslinewidth\psdoublesep\p@
\let\pst@setdoublesep\relax}
\def\tx@Shadow{Shadow }
\def\pst@closedshadow{%
\addto@pscode{%
gsave
\psk@shadowsize \psk@shadowangle \tx@PtoC
\tx@Shadow
\pst@usecolor\psshadowcolor
gsave fill grestore
stroke
grestore
gsave
\pst@usecolor\psfillcolor
gsave fill grestore
stroke
grestore}}
\def\pst@openshadow{%
\addto@pscode{%
gsave
\psk@shadowsize \psk@shadowangle \tx@PtoC
\tx@Shadow
\pst@usecolor\psshadowcolor
\ifx\psk@fillstyle\relax\else
gsave fill grestore
\fi
stroke}%
\pst@repeatarrows
\addto@pscode{grestore}
\ifx\psk@fillstyle\relax\else
\addto@pscode{%
gsave
\pst@usecolor\psfillcolor
gsave fill grestore
stroke
grestore}
\fi}
\def\pst@addborder{%
\addto@pscode{%
gsave
\psk@border 2 mul
CLW add SLW
\pst@usecolor\psbordercolor
stroke
grestore}}
\def\pst@stroke{%
\ifx\pslinestyle\@none\else
\addto@pscode{%
gsave
\pst@number\pslinewidth SLW
\pst@usecolor\pslinecolor
\@nameuse{psls@\pslinestyle}
grestore}%
\fi}
\def\pst@fill#1{\addto@pscode{gsave #1 grestore}}%
\def\pst@doublestroke{%
\addto@pscode{%
gsave
\psdoublesep SLW
\pst@usecolor\psdoublecolor
stroke
grestore}}
\def\pst@arrowtype{%
\ifx\psk@arrowB\@empty 0 \else -2 \fi
\ifx\psk@arrowA\@empty 0 \else -1 \fi
add}
\def\pst@addarrowdef{%
\addto@pscode{%
/ArrowA {
\ifx\psk@arrowA\@empty
\pst@oplineto
\else
\pst@arrowdef{A}
moveto
\fi
} def
/ArrowB {
\ifx\psk@arrowB\@empty \else \pst@arrowdef{B} \fi
} def}}
\def\pst@arrowdef#1{%
\ifnum\pst@repeatarrowsflag>\z@
/Arrow#1c [ 6 2 roll ] cvx def Arrow#1c
\fi
\tx@BeginArrow
\psk@arrowscale
\@nameuse{psas@\@nameuse{psk@arrow#1}}
\tx@EndArrow}
\def\pst@repeatarrows{%
\addto@pscode{%
gsave
\ifx\psk@arrowA\@empty\else
ArrowAc ArrowA pop pop
\fi
\ifx\psk@arrowB\@empty\else
ArrowBc ArrowB pop pop pop pop
\fi
grestore}}
\def\pst@OpenShowPoints{%
\addto@pscode{%
gsave
\psk@dotsize
\@nameuse{psds@\psk@dotstyle}
newpath
Points aload length 2 div 2 sub cvi /N ED
N 0 ge
{ \ifx\psk@arrowA\@empty
Dot
\else
pop pop
\fi
N { Dot } repeat
\ifx\psk@arrowB\@empty
Dot
\else
pop pop
\fi }
{ N 2 mul { pop } repeat }
ifelse
grestore}}
\def\pscustom{\pst@object{pscustom}}
\long\def\pscustom@i#1{%
\begin@SpecialObj
\solid@star
\let\pst@ifcustom\iftrue
\let\begin@ClosedObj\begin@CustomObj
\let\end@ClosedObj\endgroup
\def\begin@OpenObj{\begin@CustomObj\pst@addarrowdef}%
\let\end@OpenObj\endgroup
\let\begin@AltOpenObj\begin@CustomObj
\def\begin@SpecialObj{%
\begingroup
\pst@misplaced{special graphics object}%
\def\addto@pscode####1{}
\let\end@SpecialObj\endgroup}%
\def\@multips(##1)(##2)##3##4{\pst@misplaced\multips}%
\def\psclip##1{\pst@misplaced\psclip}%
\def\pst@repeatarrowsflag{\z@}%
\let\pst@setrepeatarrowsflag\relax
\showpointsfalse
\let\showpointstrue\relax
\def\pst@linetype{\pslinetype}%
\let\psset@liftpen\psset@@liftpen
\psset@liftpen{\z@}%
\def\pst@cp{/currentpoint load stopped pop }%
\def\pst@oplineto{/lineto load stopped { moveto } if }%
\def\pst@optcp##1##2{%
\ifnum##1=\z@\def##2{/currentpoint load stopped { 0 0 } if }\fi}%
\let\caddto@pscode\addto@pscode
\def\cuse@par##1{{\use@par##1}}%
\the\pst@customdefs
\setbox\pst@hbox=\hbox{#1}%
\psk@fillstyle
\pst@stroke
\end@SpecialObj}
\def\begin@CustomObj{%
\begingroup
\use@par
\addto@pscode{%
\pst@number\pslinewidth SLW
\pst@usecolor\pslinecolor}}
\def\pst@oplineto{moveto }
\def\pst@cp{}
\def\pst@optcp#1#2{}
\def\psset@liftpen#1{}
\def\psset@@liftpen#1{%
\ifcase#1\relax
\def\psk@liftpen{\z@}%
\def\pst@cp{/currentpoint load stopped pop }%
\def\pst@oplineto{/lineto load stopped { moveto } if }%
\or
\def\psk@liftpen{1}%
\def\pst@cp{}%
\def\pst@oplineto{/lineto load stopped { moveto } if }%
\or
\def\psk@liftpen{2}%
\def\pst@cp{}%
\def\pst@oplineto{moveto }%
\fi}
\psset@liftpen{0}
\def\psk@liftpen{-1}
\def\psset@linetype#1{%
\pst@getint{#1}\pslinetype
\ifnum\pst@dimg<-3
\@pstrickserr{linetype must be greater than -3}\@ehpa
\def\pslinetype{0}%
\fi}
\psset@linetype{0}
\def\caddto@pscode#1{%
\@pstrickserr{Command can only be used in \string\pscustom}\@ehpa}
\let\cuse@par\caddto@pscode
\def\tx@MSave{%
/msavemtrx
[ tx@Dict /msavemtrx known { msavemtrx aload pop } if CM ]
def }
\def\tx@MRestore{%
tx@Dict /msavemtrx known { length 0 gt } { false } ifelse
{ /msavematrx [ msavematrx aload pop setmatrix ] def }
if }
\newtoks\pst@customdefs
\pst@customdefs{%
\def\newpath{\addto@pscode{newpath}}%
\def\moveto(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor moveto}}%
\def\closepath{\addto@pscode{closepath}}%
\def\gsave{\begingroup\addto@pscode{gsave}}%
\def\grestore{\endgroup\addto@pscode{grestore}}%
% DG/SR modification begin - May 12, 1997 - Patch 2
%\def\translate(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor moveto}}%
\def\translate(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor translate}}%
% DG/SR modification end
\def\rotate#1{\pst@@getangle{#1}\addto@pscode{\pst@angle rotate}}%
\def\scale#1{\pst@getscale{#1}\pst@tempg\addto@pscode{\pst@tempg}}%
\def\msave{\addto@pscode{\tx@MSave}}%
\def\mrestore{\addto@pscode{\tx@MRestore}}%
\def\swapaxes{\addto@pscode{-90 rotate -1 1 scale}}%
\def\stroke{\pst@object{stroke}}%
\def\fill{\pst@object{fill}}%
\def\openshadow{\pst@object{openshadow}}%
\def\closedshadow{\pst@object{closedshadow}}%
% DG/SR modification begin - Jan. 7, 1998 - Patch 8
%\def\movepath(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor tx@Shadow}}%
\def\movepath(#1){\pst@@getcoor{#1}\addto@pscode{\pst@coor \tx@Shadow}}%
% DG/SR modification end
\def\lineto{\pst@onecoor{lineto}}%
\def\rlineto{\pst@onecoor{rlineto}}%
\def\curveto{\pst@threecoor{curveto}}%
\def\rcurveto{\pst@threecoor{rcurveto}}%
\def\code#1{\addto@pscode{#1}}%
\def\coor(#1){\pst@@getcoor{#1}\addto@pscode\pst@coor\@ifnextchar({\coor}{}}%
\def\rcoor{\pst@getcoors{}{}}%
\def\dim#1{\pssetlength\pst@dimg{#1}\addto@pscode{\pst@number\pst@dimg}}%
\def\setcolor#1{%
\@ifundefined{color@#1}{}{\addto@pscode{\use@color{#1}}}}%
\def\arrows#1{{\psset@arrows{#1}\pst@addarrowdef}}%
\let\file\pst@rawfile
} % END \pst@customdefs
\def\closedshadow@i{\cuse@par\pst@closedshadow}
\def\openshadow@i{\cuse@par\pst@openshadow}
\def\stroke@i{\cuse@par\pst@stroke}%
\def\fill@i{\cuse@par\psk@fillstyle}%
\def\pst@onecoor#1(#2){%
\pst@@getcoor{#2}%
\addto@pscode{\pst@coor #1}}
\def\pst@threecoor#1(#2)#3(#4)#5(#6){%
\begingroup
\pst@getcoor{#2}\pst@tempa
\pst@getcoor{#4}\pst@tempb
\pst@getcoor{#6}\pst@tembc
\addto@pscode{\pst@tempa \pst@tempb \pst@tempc #1}%
\endgroup}
\def\pst@rawfile#1{%
\begingroup
\def\do##1{\catcode`##1=12\relax}"
\dospecials
\catcode`\%=14
\pst@@rawfile{#1}%
\endgroup}
\def\pst@@rawfile#1{%
\immediate\openin1 #1
\ifeof1
\@pstrickserr{File `#1' not found}\@ehpa
\else
\immediate\read1 to \pst@tempg
\loop
\ifeof1 \@pstfalse\else\@psttrue\fi
\if@pst
\addto@pscode\pst@tempg
\immediate\read1 to \pst@tempg
\repeat
\fi
\immediate\closein1\relax}
\def\tx@NArray{NArray }
\def\tx@NArray{NArray }
\def\tx@Line{Line }
\def\tx@Arcto{Arcto }
\def\tx@CheckClosed{CheckClosed }
\def\tx@Polygon{Polygon }
\def\psset@gangle#1{\pst@getangle{#1}\psk@gangle}
\psset@gangle{0}
\def\tx@Diamond{Diamond }
\def\psdiamond{\pst@object{psdiamond}}
\def\psdiamond@i(#1){%
\@ifnextchar({\psdiamond@ii(#1)}{\psdiamond@ii(0,0)(#1)}}
\def\psdiamond@ii(#1)(#2){%
\begin@ClosedObj
\pst@getcoor{#1}\pst@tempa
\pst@getcoor{#2}\pst@tempb
\addto@pscode{%
\psline@iii
pop
\psk@dimen
\pst@tempb
\psk@gangle
\pst@tempa
\tx@Diamond}%
\def\pst@linetype{4}%
\end@ClosedObj}
\def\tx@Triangle{Triangle }
\def\pstriangle{\pst@object{pstriangle}}
\def\pstriangle@i(#1){%
\@ifnextchar({\pstriangle@ii(#1)}{\pstriangle@ii(0,0)(#1)}}
\def\pstriangle@ii(#1)(#2){%
\begin@ClosedObj
\pst@getcoor{#1}\pst@tempa
\pst@getcoor{#2}\pst@tempb
\addto@pscode{%
\psline@iii
pop
\psk@dimen
\pst@tempb
\psk@gangle
\pst@tempa
\tx@Triangle}%
\def\pst@linetype{2}%
\end@ClosedObj}
\def\tx@CCA{CCA }
\def\tx@CCA{CCA }
\def\tx@CC{CC }
\def\tx@IC{IC }
\def\tx@BOC{BOC }
\def\tx@NC{NC }
\def\tx@EOC{EOC }
\def\tx@BAC{BAC }
\def\tx@NAC{NAC }
\def\tx@EAC{EAC }
\def\tx@OpenCurve{OpenCurve }
\def\tx@AltCurve{AltCurve }
\def\tx@ClosedCurve{ClosedCurve }
\def\psset@curvature#1{%
\edef\pst@tempg{#1 }%
\expandafter\psset@@curvature\pst@tempg * * * \@nil}
\def\psset@@curvature#1 #2 #3 #4\@nil{%
\pst@checknum{#1}\pst@tempg
\pst@checknum{#2}\pst@temph
\pst@checknum{#3}\pst@tempi
\edef\psk@curvature{\pst@tempg \pst@temph \pst@tempi}}
\psset@curvature{1 .1 0}
\def\pscurve{\pst@object{pscurve}}
\def\pscurve@i{%
\pst@getarrows{%
\begin@OpenObj
\pst@getcoors[\pscurve@ii}}
\def\pscurve@ii{%
\addto@pscode{%
\pst@cp
\psk@curvature\space /c ED /b ED /a ED
\ifshowpoints true \else false \fi
\tx@OpenCurve}%
\end@OpenObj}
\def\psecurve{\pst@object{psecurve}}
\def\psecurve@i{%
\pst@getarrows{%
\begin@OpenObj
\pst@getcoors[\psecurve@ii}}
\def\psecurve@ii{%
\addto@pscode{%
\psk@curvature\space /c ED /b ED /a ED
\ifshowpoints true \else false \fi
\tx@AltCurve}%
\end@OpenObj}
\def\psccurve{\pst@object{psccurve}}
\def\psccurve@i{%
\begin@ClosedObj
\pst@getcoors[\psccurve@ii}
\def\psccurve@ii{%
\addto@pscode{%
\psk@curvature\space /c ED /b ED /a ED
\ifshowpoints true \else false \fi
\tx@ClosedCurve}%
\def\pst@linetype{1}%
\end@ClosedObj}
\def\psset@dotsize#1{%
\pst@expandafter\pst@getdimnum{#1} 0 {} {}\@nil
\edef\psk@@dotsize{\pst@number\pst@dimg}%
\let\psk@@@dotsize\pst@tempg
\edef\psk@dotsize{%
/DS \psk@@dotsize \psk@@@dotsize CLW mul add 2 div def }}
\psset@dotsize{2pt 2}
\def\psset@dotscale#1{%
\pst@getscale{#1}\psk@dotscale
\ifx\psk@dotscale\@empty
\def\psk@xdotscale{1 }%
\def\psk@ydotscale{1 }%
\else
\let\psk@xdotscale\pst@tempg
\let\psk@ydotscale\pst@temph
% DG/SR modification begin - Oct. 17, 1997 - Patch 5
%\fi}
\fi
\pst@getdotsize%
\psset@dotsize{\pst@dimg\space\pst@@dimtonum\pst@dimh}}
%\psset@dotscale{1}
% DG/SR modification end
\def\pst@Getangle#1#2{%
\pst@getangle{#1}\pst@tempg
\def\pst@temph{0. }%
\ifx\pst@tempg\pst@temph
\def#2{}%
\else
\edef#2{\pst@tempg\space rotate }%
\fi}
\def\psset@dotangle#1{%
\pst@getangle{#1}\psk@@dotangle
\ifdim\psk@@dotangle\p@=\z@
\let\psk@dotangle\@empty
\else
% DG/SR modification begin - Aug. 8, 1997 - Patch 4
%\edef\psk@dotangle{\psk@@dotangle rotate }
\edef\psk@dotangle{\psk@@dotangle rotate }%
% DG/SR modification end
\fi}
\psset@dotangle{0}
\def\pst@getdotsize{%
\pst@dimg=\psk@@@dotsize\pslinewidth
\advance\pst@dimg\psk@@dotsize\p@
\pst@dimh=\psk@ydotscale\pst@dimg
\pst@dimg=\psk@xdotscale\pst@dimg
\divide\pst@dimh 2
\divide\pst@dimg 2\relax}
% DG/SR modification begin - Oct. 17, 1997 - Patch 5
\psset@dotscale{1}
% DG/SR modification end
\def\psdot{\pst@object{psdot}}
\def\psdot@i{\@ifnextchar({\psdot@ii}{\psdot@ii(\z@,\z@)}}
\def\psdot@ii(#1){%
\begin@SpecialObj
\pst@@getcoor{#1}%
\addto@pscode{%
\psk@dotsize
\@nameuse{psds@\psk@dotstyle}%
\pst@coor Dot}%
\end@SpecialObj}
\def\psdots{\pst@object{psdots}}
\def\psdots@i{%
\begin@SpecialObj
\pst@getcoors[\psdots@ii}
\def\psdots@ii{%
\addto@pscode{false \tx@NArray \psdots@iii}%
\end@SpecialObj}
\def\psdots@iii{%
\psk@dotsize
\@nameuse{psds@\psk@dotstyle}
newpath
n { transform floor .5 add exch floor .5 add exch itransform Dot } repeat}
% DG: dead code (to suppress until \psset@dotstyle) ? - Aug. 4, 1997
\def\tx@SQ{SQ }
\def\tx@ST{ST }
\def\tx@SP{SP }
\def\pst@gdot#1{/Dot { gsave T \psk@dotangle \psk@dotscale #1 grestore } def }
\@namedef{psds@*}{\pst@gdot{0 0 DS \tx@SD}}
\@namedef{psds@o}{%
/r2 DS CLW sub def
\pst@gdot{0 0 DS \tx@SD \pst@usecolor\psfillcolor 0 0 r2 \tx@SD}}
\@namedef{psds@square*}{%
/r1 DS .886 mul def
\pst@gdot{r1 \tx@SQ}}
\@namedef{psds@square}{%
/r1 DS .886 mul def /r2 r1 CLW sub def
\pst@gdot{r1 \tx@SQ \pst@usecolor\psfillcolor r2 \tx@SQ}}
\@namedef{psds@triangle*}{%
/y1 DS .778 mul neg def /x1 y1 1.732 mul neg def
\pst@gdot{x1 y1 \tx@ST}}
\@namedef{psds@triangle}{%
/y1 DS .778 mul neg def /x1 y1 1.732 mul neg def
/y2 y1 CLW add def /x2 y2 1.732 mul neg def
\pst@gdot{x1 y1 \tx@ST \pst@usecolor\psfillcolor x2 y2 \tx@ST}}
\@namedef{psds@pentagon*}{%
/r1 DS 1.149 mul def
\pst@gdot{r1 \tx@SP}}
\@namedef{psds@pentagon}{%
DS .93 mul dup 1.236 mul /r1 ED CLW sub 1.236 mul /r2 ED
\pst@gdot{r1 \tx@SP \pst@usecolor\psfillcolor r2 \tx@SP}}
\@namedef{psds@+}{%
/DS DS 1.253 mul def
\pst@gdot{DS 0 moveto DS neg 0 L stroke 0 DS moveto 0 DS neg L stroke}}
\@namedef{psds@|}{%
\psk@tbarsize CLW mul add 2 div /DS ED
\pst@gdot{0 DS moveto 0 DS neg L stroke}}
% DG: end dead code?
\def\psset@dotstyle#1{%
\@ifundefined{psds@#1}%
{\@pstrickserr{Dot style `#1' not defined}\@eha}%
{\edef\psk@dotstyle{#1}}}
\psset@dotstyle{*}
\def\tx@FontDot{FontDot }
\def\newpsfontdot#1[#2]#3#4{%
\@namedef{psds@#1}{%
/#3 \psk@@dotangle [#2] \tx@FontDot
/Dot { moveto #4 show } bind def }}
\def\newpsfontdotH#1[#2]#3#4#5{%
\@namedef{psds@#1}{%
/#3 \psk@@dotangle [#2] \tx@FontDot
/Dot {
moveto
\iftrue
gsave \pst@usecolor\psfillcolor #5 show grestore
\fi
#4 show
} bind def }}
\pstheader{pst-dots.pro}
\newpsfontdot{*}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(b)}
\newpsfontdotH{o}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(c)}{(b)}
\newpsfontdotH{Bo}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(C)}{(b)}
\newpsfontdotH{triangle}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(t)}{(u)}
\newpsfontdotH{Btriangle}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(T)}{(u)}
\newpsfontdot{triangle*}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(u)}
\newpsfontdotH{square}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(s)}{(r)}
\newpsfontdotH{Bsquare}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(S)}{(r)}
\newpsfontdot{square*}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(r)}
\newpsfontdotH{pentagon}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(p)}{(q)}
\newpsfontdotH{Bpentagon}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(P)}{(q)}
\newpsfontdot{pentagon*}%
[1.0 0.0 0.0 1.0 0.0 0.0]{PSTricksDotFont}{(q)}
% DG/SR modification begin - Mar. 18, 1997
%\newpsfontdot{diamond*}%
%[1.9 0.0 0.0 1.9 -0.4598 -0.70775]{Symbol}{<E0>}
%\newpsfontdot{diamond}%
%[2.3 0.0 0.0 2.3 -0.8533 -0.5336]{Symbol}{<A8>}
\newpsfontdot{diamond}%
[1.9 0.0 0.0 1.9 -0.4598 -0.70775]{Symbol}{<E0>}
\newpsfontdot{diamond*}%
[2.3 0.0 0.0 2.3 -0.8533 -0.5336]{Symbol}{<A8>}
% DG/SR modification end
\newpsfontdot{oplus}%
[1.44928 0.0 0.0 1.44928 -0.562319 -0.478261]{Symbol}{<C5>}
\newpsfontdot{otimes}%
[1.44928 0.0 0.0 1.44928 -0.562319 -0.475362]{Symbol}{<C4>}
\newpsfontdot{x}%
[1.8 0.0 0.0 1.8 -0.495 -0.4788]{Symbol}{<B4>}
\newpsfontdot{+}%
[2.3 0.0 0.0 2.3 -0.6486 -0.5819]{Times-Roman}{<2B>}
\newpsfontdot{asterisk}%
[2.43309 0.0 0.0 2.43309 -0.609489 -1.14477]{Times-Roman}{<2A>}
\newpsfontdot{B+}%
[2.3 0.0 0.0 2.3 -0.6555 -0.5819]{Times-Bold}{<2B>}
\newpsfontdot{Basterisk}%
[2.29358 0.0 0.0 2.29358 -0.576835 -1.08486]{Times-Bold}{<2A>}
\newpsfontdot{|}%
% DG/SR modification begin - Oct. 27, 1997 - Patch 7
%[1.98413 0.0 0.0 1.98413 -0.258929 -0.712302]{Helvetica}{(|)}
[1.98413 0.0 0.0 1.38 -0.258929 -0.5]{Helvetica}{(|)}
% DG/SR modification end
\newpsfontdot{B|}%
% DG/SR modification begin - Oct. 27, 1997 - Patch 7
%[1.98413 0.0 0.0 1.98413 -0.277778 -0.78302]{Helvetica-Bold}{(|)}
[1.98413 0.0 0.0 1.38 -0.277778 -0.5]{Helvetica-Bold}{(|)}
% DG/SR modification end
\iffalse
\newpsfontdot{*}%
[2.77778 0.0 0.0 2.77778 -0.638889 -0.813889]{Symbol}{<B7>}
\newpsfontdot{o}%
[3.33333 0.0 0.0 3.33333 -0.666667 -1.78167]{Symbol}{<B0>}
\newpsfontdot{Bo}%
[4.69484 0.0 0.0 4.69484 -0.78169 -2.97418]{Times-Bold}{<CA>}
\fi
\newdimen\pslinearc
\def\psset@linearc#1{\pssetlength\pslinearc{#1}}
\psset@linearc{0pt}
\def\psline{\pst@object{psline}}
\def\psline@i{%
\pst@getarrows{%
\begin@OpenObj
\pst@getcoors[\psline@ii}}
\def\psline@ii{%
\addto@pscode{\pst@cp \psline@iii \tx@Line}%
\end@OpenObj}
\def\psline@iii{%
\ifdim\pslinearc>\z@
/r \pst@number\pslinearc def
/Lineto { \tx@Arcto } def
\else
/Lineto /lineto load def
\fi
\ifshowpoints true \else false \fi}
\def\qline(#1)(#2){%
\def\pst@par{}%
\begin@SpecialObj
\def\pst@linetype{0}%
\pst@getcoor{#1}\pst@tempa
\pst@@getcoor{#2}%
\addto@pscode{%
\pst@tempa moveto \pst@coor L
\@nameuse{psls@\pslinestyle}}%
\end@SpecialObj}
\def\pspolygon{\pst@object{pspolygon}}
\def\pspolygon@i{%
\begin@ClosedObj
\def\pst@cp{}%
\pst@getcoors[\pspolygon@ii}
\def\pspolygon@ii{%
\addto@pscode{\psline@iii \tx@Polygon}%
\def\pst@linetype{1}%
\end@ClosedObj}
\def\psset@framearc#1{\pst@checknum{#1}\psk@framearc}
\psset@framearc{0}
\def\psset@cornersize#1{%
\pst@expandafter\psset@@cornersize{#1}\@nil}
\def\psset@@cornersize#1#2\@nil{%
\if #1a\relax
\def\psk@cornersize{\pst@number\pslinearc false }%
\else
\def\psk@cornersize{\psk@framearc true }%
\fi}
\psset@cornersize{relative}
\def\tx@Rect{Rect }
\def\tx@OvalFrame{OvalFrame }
\def\tx@Frame{Frame }
\def\psset@dimen#1{%
\pst@expandafter\psset@@dimen{#1}\@nil}
\def\psset@@dimen#1#2\@nil{%
\if #1o\relax
\def\psk@dimen{.5 }%
\else
\if #1m\relax
\def\psk@dimen{0 }%
\else
\if #1i\relax
\def\psk@dimen{-.5 }%
\fi
\fi
\fi}
\psset@dimen{outer}
\def\psframe{\pst@object{psframe}}
\def\psframe@i(#1){%
\@ifnextchar({\psframe@ii(#1)}{\psframe@ii(0,0)(#1)}}
\def\psframe@ii(#1)(#2){%
\begin@ClosedObj
\pst@getcoor{#1}\pst@tempa
\pst@@getcoor{#2}%
\addto@pscode{\psk@cornersize \pst@tempa \pst@coor \psk@dimen \tx@Frame}%
\def\pst@linetype{2}%
\showpointsfalse
\end@ClosedObj}
\def\tx@BezierNArray{BezierNArray }
\def\tx@OpenBezier{OpenBezier }
\def\tx@ClosedBezier{ClosedBezier }
\def\tx@BezierShowPoints{BezierShowPoints }
\def\psbezier{\pst@object{psbezier}}
\def\psbezier@i{%
\pst@getarrows{%
\begin@OpenObj
\pst@getcoors[\psbezier@ii}}
\def\psbezier@ii{%
\addto@pscode{%
% DG/SR modification begin - Apr. 28, 1997 - Patch 1
% \psbezier doesn't work inside \pscustom
%\pst@cp
% DG/SR modification end
\ifshowpoints true \else false \fi
\tx@OpenBezier
\ifshowpoints \tx@BezierShowPoints \fi}%
\end@OpenObj}
\def\pscbezier{\pst@object{pscbezier}}
\def\pscbezier@i{%
\begin@ClosedObj
\pst@getcoors[\pscbezier@ii}
\def\pscbezier@ii{%
\addto@pscode{%
\ifshowpoints true \else false \fi
\tx@ClosedBezier
\ifshowpoints \tx@BezierShowPoints \fi}%
\chardef\pst@linetype=1
\end@ClosedObj}
\def\tx@Parab{Parab }
\def\parabola{\pst@object{parabola}}
\def\parabola@i{\pst@getarrows\parabola@ii}
\def\parabola@ii#1(#2)#3(#4){%
\begin@OpenObj
\pst@getcoor{#2}\pst@tempa
\pst@@getcoor{#4}%
\addto@pscode{\pst@tempa \pst@coor \tx@Parab}%
\end@OpenObj}
\def\psset@gridwidth#1{\pst@getlength{#1}\psk@gridwidth}
\psset@gridwidth{.8pt}
\def\psset@griddots#1{%
\pst@cntg=#1\relax
\edef\psk@griddots{\the\pst@cntg}}
\psset@griddots{0}
\def\psset@gridcolor#1{\pst@getcolor{#1}\psgridcolor}
\psset@gridcolor{black}
\def\psset@subgridwidth#1{\pst@getlength{#1}\psk@subgridwidth}
\psset@subgridwidth{.4pt}
\def\psset@subgridcolor#1{\pst@getcolor{#1}\pssubgridcolor}
\psset@subgridcolor{gray}
\def\psset@subgriddots#1{%
\pst@cntg=#1\relax\edef\psk@subgriddots{\the\pst@cntg}}
\psset@subgriddots{0}
\def\psset@subgriddiv#1{%
\pst@cntg=#1\relax\edef\psk@subgriddiv{\the\pst@cntg}}
\psset@subgriddiv{5}
\def\psset@gridlabels#1{\pst@getlength{#1}\psk@gridlabels}
\psset@gridlabels{10pt}
\def\psset@gridlabelcolor#1{\pst@getcolor{#1}\psgridlabelcolor}
\psset@gridlabelcolor{black}
\def\tx@Grid{Grid }
\def\psgrid{\pst@object{psgrid}}
\def\psgrid@i{\@ifnextchar(%
{\psgrid@ii}{\expandafter\psgrid@iv\pic@coor}}
\def\psgrid@ii(#1){\@ifnextchar(%
{\psgrid@iii(#1)}{\psgrid@iv(0,0)(0,0)(#1)}}
\def\psgrid@iii(#1)(#2){\@ifnextchar(%
{\psgrid@iv(#1)(#2)}{\psgrid@iv(#1)(#1)(#2)}}
\def\psgrid@iv(#1)(#2)(#3){%
\begin@SpecialObj
\pst@getcoor{#1}\pst@tempa
\pst@getcoor{#2}\pst@tempb
\pst@@getcoor{#3}%
\ifnum\psk@subgriddiv>1
\addto@pscode{gsave
\psk@subgridwidth SLW \pst@usecolor\pssubgridcolor
\pst@tempb \pst@coor \pst@tempa
\pst@number\psxunit \pst@number\psyunit
\psk@subgriddiv\space \psk@subgriddots\space
{} 0 \tx@Grid grestore}%
\fi
\addto@pscode{gsave
\psk@gridwidth SLW \pst@usecolor\psgridcolor
\pst@tempb \pst@coor \pst@tempa
\pst@number\psxunit \pst@number\psyunit
1 \psk@griddots\space { \pst@usecolor\psgridlabelcolor }
\psk@gridlabels \tx@Grid grestore}%
\end@SpecialObj}
\newif\ifpsmathbox
\psmathboxtrue
\def\pst@mathflag{\z@}
\newtoks\everypsbox
\let\pst@thisbox\relax
\long\def\pst@makenotverbbox#1#2{%
\edef\pst@mathflag{%
\ifpsmathbox\ifmmode\ifinner 1\else 2\fi\else \z@\fi\else \z@\fi}%
\setbox\pst@hbox=\hbox{%
\ifcase\pst@mathflag\or$\m@th\textstyle\or$\m@th\displaystyle\fi
{\pst@thisbox\the\everypsbox#2}%
\ifnum\pst@mathflag>\z@$\fi}%
#1}
\def\pst@makeverbbox#1{%
\def\pst@afterbox{#1}%
\edef\pst@mathflag{%
\ifpsmathbox\ifmmode\ifinner 1\else 2\fi\else \z@\fi\else \z@\fi}%
\afterassignment\pst@beginbox
\setbox\pst@hbox\hbox}
\def\pst@beginbox{%
\ifcase\pst@mathflag\or$\m@th\or$\m@th\displaystyle\fi
\bgroup\aftergroup\pst@endbox
\pst@thisbox
\the\everypsbox}
\def\pst@endbox{%
\ifnum\pst@mathflag>\z@$\fi
\egroup
\pst@afterbox}
\def\pst@makebox{\pst@@makebox}
\def\psverbboxtrue{\def\pst@@makebox{\pst@makeverbbox}}
\def\psverbboxfalse{\def\pst@@makebox{\pst@makenotverbbox}}
\psverbboxfalse
\def\pst@longbox{%
\def\pst@makebox{%
\gdef\pst@makebox{\pst@@makebox}%
\pst@makelongbox}}
\def\pst@makelongbox#1{%
\def\pst@afterbox{#1}%
\edef\pst@mathflag{%
\ifpsmathbox\ifmmode\ifinner 1\else 2\fi\else \z@\fi\else \z@\fi}%
\setbox\pst@hbox\hbox\bgroup
\aftergroup\pst@afterbox
\ifcase\pst@mathflag\or$\m@th\or$\m@th\displaystyle\fi
\begingroup
\pst@thisbox
\the\everypsbox}
\def\pst@endlongbox{%
\endgroup
\ifnum\pst@mathflag>\z@$\fi
\egroup}
\def\pslongbox#1#2{%
\@namedef{#1}{\pst@longbox#2}%
\@namedef{end#1}{\pst@endlongbox}}
\newdimen\psframesep
\def\psset@framesep#1{\pssetlength\psframesep{#1}}
\psset@framesep{3pt}
\newif\ifpsboxsep
\def\psset@boxsep#1{\@nameuse{psboxsep#1}}
\psset@boxsep{true}
\def\pst@useboxpar{%
\use@par
\if@star
\let\pslinecolor\psfillcolor
\solid@star
\let\solid@star\relax
\fi
\ifpsdoubleline \pst@setdoublesep \fi}
\def\psframebox{\pst@object{psframebox}}
\def\psframebox@i{\pst@makebox\psframebox@ii}
\def\psframebox@ii{%
\begingroup
\pst@useboxpar
\pst@dima=\pslinewidth
\advance\pst@dima by \psframesep
\pst@dimc=\wd\pst@hbox\advance\pst@dimc by \pst@dima
\pst@dimb=\dp\pst@hbox\advance\pst@dimb by \pst@dima
\pst@dimd=\ht\pst@hbox\advance\pst@dimd by \pst@dima
\setbox\pst@hbox=\hbox{%
\ifpsboxsep\kern\pst@dima\fi
\begin@ClosedObj
\addto@pscode{%
\psk@cornersize
\pst@number\pst@dima neg
\pst@number\pst@dimb neg
\pst@number\pst@dimc
\pst@number\pst@dimd
.5
\tx@Frame}%
\def\pst@linetype{2}%
\showpointsfalse
\end@ClosedObj
\box\pst@hbox
\ifpsboxsep\kern\pst@dima\fi}%
\ifpsboxsep\dp\pst@hbox=\pst@dimb\ht\pst@hbox=\pst@dimd\fi
\leavevmode\box\pst@hbox
\endgroup}
\def\psdblframebox{\pst@object{psdblframebox}}
\def\psdblframebox@i{\addto@par{doubleline=true}\psframebox@i}
\def\psclip#1{%
\leavevmode
\begingroup
\begin@psclip
\begingroup
\def\use@pscode{%
\pstVerb{%
\pst@dict
/mtrxc CM def
CP CP T
\tx@STV
\psk@origin
\psk@swapaxes
newpath
\pst@code
clip
newpath
mtrxc setmatrix
moveto
0 setgray
end}%
\gdef\pst@code{}}%
\def\@multips(##1)(##2)##3##4{\pst@misplaced\multips}%
\def\nc@object##1##2##3##4{\pst@misplaced{node connection}}%
\hbox to\z@{#1}%
\endgroup
\def\endpsclip{%
\end@psclip
\endgroup}%
\ignorespaces}
\def\endpsclip{\pst@misplaced\endpsclip}
\let\begin@psclip\relax
\def\end@psclip{\pstVerb{currentpoint initclip moveto}}
\def\AltClipMode{%
\def\end@psclip{\pstVerb{\pst@grestore}}%
\def\begin@psclip{\pstVerb{gsave}}}
\def\clipbox{\@ifnextchar[{\clipbox@}{\clipbox@[\z@]}}
% DG modification begin - Apr. 3, 1997
% From paulus@immd5.informatik.uni-erlangen.de (Dietrich Paulus)
%\def\clipbox@[#1]{\pst@makebox\clipbox@@{#1}}
\def\clipbox@[#1]{\pst@makebox{\clipbox@@{#1}}}
% DG modification end
\def\clipbox@@#1{%
\pssetlength\pst@dimg{#1}%
\leavevmode\hbox{%
\begin@psclip
\pst@Verb{%
CM \tx@STV CP T newpath
/a \pst@number\pst@dimg def
/w \pst@number{\wd\pst@hbox}a add def
/d \pst@number{\dp\pst@hbox}a add neg def
/h \pst@number{\ht\pst@hbox}a add def
a neg d moveto
a neg h L
w h L
w d L
closepath
clip
newpath
0 0 moveto
setmatrix}%
\unhbox\pst@hbox
\end@psclip}}
\def\psshadowbox{\pst@object{psshadowbox}}
\def\psshadowbox@i{\pst@makebox\psshadowbox@ii}
\def\psshadowbox@ii{%
\begingroup
\pst@useboxpar
\psshadowtrue
\psboxseptrue
\def\psk@shadowangle{-45 }%
\setbox\pst@hbox=\hbox{\psframebox@ii}%
\pst@dimh=\psk@shadowsize\p@
\pst@dimh=.7071\pst@dimh
\pst@dimg=\dp\pst@hbox
\advance\pst@dimg\pst@dimh
\dp\pst@hbox=\pst@dimg
\pst@dimg=\wd\pst@hbox
\advance\pst@dimg\pst@dimh
\wd\pst@hbox=\pst@dimg
\leavevmode
\box\pst@hbox
\endgroup}
\def\pscirclebox{\pst@object{pscirclebox}}
\def\pscirclebox@i{\pst@makebox\pscirclebox@ii}
\def\pscirclebox@ii{%
\begingroup
\pst@useboxpar
\setbox\pst@hbox=\hbox{%
\pst@nodehook
\pscirclebox@iii
\box\pst@hbox}%
\ifpsboxsep \pscirclebox@sep \fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\pscirclebox@iii{%
\if@star
\pslinewidth\z@
\pstverb{\pst@dict \tx@STP \pst@usecolor\psfillcolor
newpath \pscirclebox@iv \tx@SD end}%
\else
\begin@ClosedObj
\def\pst@linetype{4}\showpointsfalse
\addto@pscode{%
\pscirclebox@iv CLW 2 div add 0 360 arc closepath}%
\end@ClosedObj
\fi}
\def\pscirclebox@iv{%
\pst@number{\wd\pst@hbox}2 div
\pst@number{\ht\pst@hbox}\pst@number{\dp\pst@hbox}add 2 div
2 copy \pst@number{\dp\pst@hbox}sub 4 2 roll
\tx@Pyth \pst@number\psframesep add }
\def\pscirclebox@sep{%
\pst@dimb=\ht\pst@hbox
\advance\pst@dimb\dp\pst@hbox
\divide\pst@dimb 2
\pst@dima=.5\wd\pst@hbox
\pst@pyth\pst@dima\pst@dimb\pst@dimc
\advance\pst@dimc\pslinewidth
\advance\pst@dimc\psframesep
\advance\pst@dimb-\pst@dimc
\setbox\pst@hbox=\hbox to2\pst@dimc{%
\hss
\vbox{\kern-\pst@dimb\box\pst@hbox}%
\hss}%
\advance\pst@dimb-\dp\pst@hbox
\dp\pst@hbox=-\pst@dimb}
\let\pst@nodehook\relax
\def\psCirclebox{\pst@object{psCirclebox}}
\def\psCirclebox@i{\pst@makebox\psCirclebox@ii}
\def\psCirclebox@ii{%
\begingroup
\pst@useboxpar
\pst@dima=\ht\pst@hbox
\advance\pst@dima\dp\pst@hbox
\divide\pst@dima\tw@
\pssetlength\pst@dimb\psk@radius
\setbox\pst@hbox=\hbox{%
\pst@nodehook
\pscircle(.5\wd\pst@hbox,\pst@dima){\pst@dimb}%
\box\pst@hbox}%
\ifpsboxsep \psCirclebox@sep \fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\psCirclebox@sep{%
\pst@dimc=\pst@dimb
\advance\pst@dimb-\pst@dima
\advance\pst@dima\pst@dimc
\setbox\pst@hbox=\hbox to\tw@\pst@dimc{%
\hss
\vrule width \z@ depth \pst@dimb height \pst@dima
\box\pst@hbox
\hss}}%
\def\psovalbox{\pst@object{psovalbox}}
\def\psovalbox@i{\pst@makebox{\psovalbox@ii}}
\def\psovalbox@ii{%
\begingroup
\pst@useboxpar
\psovalbox@iii
\ifpsboxsep\psovalbox@sep\fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\psovalbox@iii{%
\psovalbox@iv
\setbox\pst@hbox=\hbox{%
\begin@ClosedObj
\addto@pscode{%
0 360
\pst@number\pst@dimc CLW 2 div sub
\pst@number\pst@dimd CLW 2 div sub
\pst@number\pst@dima
\pst@number\pst@dimb
\tx@Ellipse
closepath}%
\def\pst@linetype{2}%
\end@ClosedObj
\unhbox\pst@hbox}}
\def\psovalbox@iv{%
\pst@dimc=\pslinewidth\advance\pst@dimc\psframesep
\pst@dimd=\ht\pst@hbox\advance\pst@dimd\dp\pst@hbox
\pst@dima=.5\wd\pst@hbox
\pst@dimb=.5\pst@dimd\advance\pst@dimb-\dp\pst@hbox
\pst@dimd=.707\pst@dimd
\advance\pst@dimd\pst@dimc
\advance\pst@dimc.707\wd\pst@hbox}
\def\psovalbox@sep{%
\setbox\pst@hbox\hbox to 2\pst@dimc{\hss\unhbox\pst@hbox\hss}%
\pst@dimg=\pst@dimd
\advance\pst@dimg-\pst@dimb
\dp\pst@hbox=\pst@dimg
\advance\pst@dimd\pst@dimb
\ht\pst@hbox=\pst@dimd}
\def\psdiabox{\pst@object{psdiabox}}
\def\psdiabox@i{\pst@makebox{\psdiabox@ii}}
\def\psdiabox@ii{%
\begingroup
\pst@useboxpar
\psdiabox@iii
\ifpsboxsep\psdiabox@sep\fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\psdiabox@iv{%
\pst@dimg=.707\pslinewidth
\advance\pst@dimg.707\psframesep
\pst@dima=\wd\pst@hbox
\divide\pst@dima 2
\pst@dimc=\pst@dima
\advance\pst@dimc\pst@dimg
\pst@dimd=\ht\pst@hbox
\advance\pst@dimd\dp\pst@hbox
\divide\pst@dimd 2
\pst@dimb=\pst@dimd
\advance\pst@dimb-\dp\pst@hbox
\advance\pst@dimd\pst@dimg}
\def\psdiabox@iii{%
\psdiabox@iv
\setbox\pst@hbox=\hbox{%
\begin@ClosedObj
\addto@pscode{%
\psline@iii
pop
.5
\pst@number\pst@dimc 2 mul \pst@number\pst@dimd 2 mul
0
\pst@number\pst@dima \pst@number\pst@dimb
\tx@Diamond}%
\def\pst@linetype{4}%
\end@ClosedObj
\box\pst@hbox}}
\def\psdiabox@sep{%
\setbox\pst@hbox\hbox to 4\pst@dimc{\hss\unhbox\pst@hbox\hss}%
\multiply\pst@dimd 2
\advance\pst@dimd\pst@dimb
\ht\pst@hbox\pst@dimd
\advance\pst@dimd-2\pst@dimb
\dp\pst@hbox\pst@dimd}
\def\psset@trimode#1{\pst@expandafter\psset@@trimode{#1}\@empty\@empty\@nil}
\def\psset@@trimode#1#2#3\@nil{%
\let\pst@tempg#1\relax
\ifx\pst@tempg*%
\let\psk@@trimode\@empty
\let\pst@tempg#2\relax
\else
\let\psk@@trimode\relax
\fi
\edef\psk@trimode{%
\ifx R\pst@tempg 1 \else\ifx D\pst@tempg 2
\else\ifx L\pst@tempg 3 \else 0 \fi\fi\fi}}
\psset@trimode{U}
\def\pstribox{\pst@object{pstribox}}
\def\pstribox@i{\pst@makebox{\pstribox@ii}}
\def\pstribox@ii{%
\begingroup
\pst@useboxpar
\pstribox@iii
\ifpsboxsep\pstribox@sep\fi
\leavevmode
\box\pst@hbox
\endgroup}
\def\pstribox@iii{%
\pstribox@iv
\setbox\pst@hbox=\hbox{%
\begin@ClosedObj
\addto@pscode{%
\psline@iii
pop
.5
\pst@number\pst@dimc \pst@number\pst@dimd
\ifodd\psk@trimode exch \fi
\psk@trimode -90 mul
\pst@number\pst@dima \pst@number\pst@dimb
\tx@Triangle}%
\def\pst@linetype{2}%
\end@ClosedObj
\box\pst@hbox}}
\def\pstribox@iv{%
\pst@dimh=\pslinewidth
\advance\pst@dimh\psframesep
\pst@dimg=\ht\pst@hbox
\advance\pst@dimg-\dp\pst@hbox
\divide\pst@dimg 2
\edef\pst@tempa{\number\pst@dimg sp}% For use by nodes.
\ifodd\psk@trimode
\pst@dimb\pst@dimg
\else
\pst@dima=\wd\pst@hbox
\divide\pst@dima 2
\fi
\ifcase\psk@trimode
\pst@dimb=-\dp\pst@hbox
\advance\pst@dimb-\pst@dimh
\or
\pst@dima=-\pst@dimh
\or
\pst@dimb=\ht\pst@hbox
\advance\pst@dimb\pst@dimh
\or
\pst@dima=\wd\pst@hbox
\advance\pst@dima\pst@dimh
\fi
\pst@dimd=\dp\pst@hbox
\advance\pst@dimd\ht\pst@hbox
\ifx\psk@@trimode\relax
\pst@dimc=\wd\pst@hbox
\advance\pst@dimc\ifodd\psk@trimode 1.447\else 1.789\fi\pst@dimh
\multiply\pst@dimc 2
\advance\pst@dimd\ifodd\psk@trimode 1.789\else 1.447\fi\pst@dimh
\multiply\pst@dimd 2
\else
\ifodd\psk@trimode
\advance\pst@dimd 1.1547\wd\pst@hbox
\advance\pst@dimd 3.4641\pst@dimh
\pst@dimc=.866\pst@dimd
\else
\advance\pst@dimd .866\wd\pst@hbox %.866=(sqrt(3)/2)
\advance\pst@dimd 3\pst@dimh
\pst@dimc=1.1547\pst@dimd % 1.1547=(2/sqrt(3))
\fi
\fi}
\def\pstribox@sep{%
\ifodd\psk@trimode
\advance\pst@dimb.5\pst@dimd
\ht\pst@hbox=\pst@dimb
\advance\pst@dimd-\pst@dimb
\dp\pst@hbox=\pst@dimd
\else
\setbox\pst@hbox\hbox to \pst@dimc{\hss\unhbox\pst@hbox\hss}%
\global\pst@dimg=.5\pst@dimc
\fi
\ifcase\psk@trimode
\dp\pst@hbox-\pst@dimb
\advance\pst@dimd\pst@dimb
\ht\pst@hbox\pst@dimd
\or
\pst@dimg=.5\wd\pst@hbox
\global\advance\pst@dimg-\pst@dima
\setbox\pst@hbox\hbox to \pst@dimc{\kern-\pst@dima\box\pst@hbox\hss}%
\or
\ht\pst@hbox\pst@dimb
\advance\pst@dimd-\pst@dimb
\dp\pst@hbox\pst@dimd
\or
\pst@dimg=\pst@dimc
\advance\pst@dimg-\pst@dima
\global\advance\pst@dimg.5\wd\pst@hbox
\setbox\pst@hbox\hbox to \pst@dimc{%
\hss\box\pst@hbox\kern\psframesep\kern\pslinewidth}%
\fi}
\def\psset@arcsepA#1{\pst@getlength{#1}\psk@arcsepA}
\def\psset@arcsepB#1{\pst@getlength{#1}\psk@arcsepB}
\def\psset@arcsep#1{%
\psset@arcsepA{#1}\let\psk@arcsepB\psk@arcsepA}
\psset@arcsep{0}
\def\tx@ArcArrow{ArcArrow }
\def\psarc{\pst@object{psarc}}
\def\psarc@i{%
\@ifnextchar({\psarc@iii}{\psarc@ii}}
\def\psarc@ii#1{\addto@par{arrows=#1}%
\@ifnextchar({\psarc@iii}{\psarc@iii(0,0)}}
\def\psarc@iii(#1)#2#3#4{%
\begin@OpenObj
\pst@getangle{#3}\pst@tempa
\pst@getangle{#4}\pst@tempb
\pst@@getcoor{#1}%
\pssetlength\pst@dima{#2}%
\addto@pscode{\psarc@iv \psarc@v}%
\gdef\psarc@type{0}%
\showpointsfalse
\end@OpenObj}
\def\psarc@iv{%
\pst@coor /y ED /x ED
/r \pst@number\pst@dima def
/c 57.2957 r \tx@Div def
/angleA
\pst@tempa
\psk@arcsepA c mul 2 div
\ifcase \psarc@type add \or sub \fi
def
/angleB
\pst@tempb
\psk@arcsepB c mul 2 div
\ifcase \psarc@type sub \or add \fi
def
\ifshowpoints\psarc@showpoints\fi
\ifx\psk@arrowA\@empty
\ifnum\psk@liftpen=2
r angleA \tx@PtoC
y add exch x add exch
moveto
\fi
\fi}
\def\psarc@v{%
x y r
angleA
\ifx\psk@arrowA\@empty\else
{ ArrowA CP }
{ \ifcase\psarc@type add \or sub \fi }
\tx@ArcArrow
\fi
angleB
\ifx\psk@arrowB\@empty\else
{ ArrowB }
{ \ifcase\psarc@type sub \or add \fi }
\tx@ArcArrow
\fi
\ifcase\psarc@type arc \or arcn \fi}
\def\psarc@type{0}
\def\psarc@showpoints{%
gsave
newpath
x y moveto
x y r \pst@tempa \pst@tempb
\ifcase\psarc@type arc \or arcn \fi
closepath
CLW 2 div SLW
[ \psk@dash\space ] 0 setdash stroke
grestore }
\def\psarcn{\pst@object{psarcn}}
\def\psarcn@i{\def\psarc@type{1}\psarc@i}
\def\pscircle{\pst@object{pscircle}}
\def\pscircle@i{\@ifnextchar({\pscircle@do}{\pscircle@do(0,0)}}
\def\pscircle@do(#1)#2{%
\if@star
{\use@par\qdisk(#1){#2}}%
\else
\begin@ClosedObj
\pst@@getcoor{#1}%
\pssetlength\pst@dimc{#2}%
\def\pst@linetype{4}%
\addto@pscode{%
\pst@coor
\pst@number\pst@dimc
\psk@dimen CLW mul sub
0 360 arc
closepath}%
\showpointsfalse
\end@ClosedObj
\fi
\ignorespaces}
\def\qdisk(#1)#2{%
\def\pst@par{}%
\begin@SpecialObj
\pst@@getcoor{#1}%
\pssetlength\pst@dimg{#2}%
\addto@pscode{\pst@coor \pst@number\pst@dimg \tx@SD}%
\end@SpecialObj}
\def\psset@radius#1{\pst@@getlength{#1}\psk@radius}
\psset@radius{.25cm}
\def\psCircle{\pst@object{psCircle}}
\def\psCircle@i{\@ifnextchar({\psCircle@ii}{\psCircle@ii(0,0)}}
\def\psCircle@ii(#1){\pscircle@do(#1){\psk@radius}}
\def\pswedge{\pst@object{pswedge}}
\def\pswedge@i{\@ifnextchar({\pswedge@ii}{\pswedge@ii(0,0)}}
\def\pswedge@ii(#1)#2#3#4{%
\begin@ClosedObj
\pssetlength\pst@dimc{#2}
\pst@getangle{#3}\pst@tempa
\pst@getangle{#4}\pst@tempb
\pst@@getcoor{#1}%
\def\pst@linetype{1}%
\addto@pscode{%
\pst@coor
2 copy
moveto
\pst@number\pst@dimc \psk@dimen CLW mul sub % Adjusted radius
\pst@tempa \pst@tempb
arc
closepath}%
\showpointsfalse
\end@ClosedObj}
\def\tx@Ellipse{Ellipse }
\def\psellipse{\pst@object{psellipse}}
\def\psellipse@i(#1){\@ifnextchar(%
{\psellipse@ii(#1)}{\psellipse@ii(0,0)(#1)}}
\def\psellipse@ii(#1)(#2){%
\begin@ClosedObj
\pst@getcoor{#1}\pst@tempa
\pst@@getcoor{#2}%
\addto@pscode{%
0 360
\pst@coor
\ifdim\psk@dimen\p@=\z@\else
\psk@dimen CLW mul
dup 4 -1 roll sub neg 3 1 roll sub
\fi
\pst@tempa
\tx@Ellipse
closepath}%
\def\pst@linetype{2}%
\end@ClosedObj}
\def\multips{\@ifnextchar({\def\pst@par{}\multips@ii}{\multips@i}}
\def\multips@i#1{\def\pst@par{rot=#1}\multips@ii}
\def\multips@ii(#1){\@ifnextchar({\multips@iii(#1)}{\multips@iii(\z@,\z@)(#1)}}
\long\def\multips@iii(#1)(#2)#3#4{%
\begingroup
\use@par
\pst@getcoor{#1}\pst@tempa
\pst@@getcoor{#2}%
\pst@cnta=#3\relax
\init@pscode
\addto@pscode{%
\pst@tempa T \the\pst@cnta\space \pslbrace
gsave \ifx\psk@rot\@empty\else\psk@rot rotate \fi}%
\hbox to\z@{%
\def\init@pscode{%
\addto@pscode{%
gsave
\pst@number\pslinewidth SLW
\pst@usecolor\pslinecolor}}%
\def\use@pscode{\addto@pscode{grestore}}%
\def\psclip##1{\pst@misplaced\psclip}%
\def\nc@object##1##2##3##4{\pst@misplaced{node connection}}%
#4}%
\addto@pscode{grestore \pst@coor T \psrbrace repeat}%
\leavevmode
\use@pscode
\endgroup
\ignorespaces}
\def\scalebox#1{\pst@makebox{\@scalebox{#1}}}
\def\@scalebox#1{%
\begingroup
\pst@getscale{#1}\pst@tempa
\let\pst@tempc\pst@tempg
\let\pst@tempd\pst@temph
\@@scalebox
\endgroup}
\def\@@scalebox{%
\leavevmode
\hbox{%
\ifdim\pst@tempd\p@<\z@
\pst@dimg=\pst@tempd\ht\pst@hbox
\pst@dimh=\pst@tempd\dp\pst@hbox
\dp\pst@hbox=-\pst@dimg
\ht\pst@hbox=-\pst@dimh
\else
\ht\pst@hbox=\pst@tempd\ht\pst@hbox
\dp\pst@hbox=\pst@tempd\dp\pst@hbox
\fi
\pst@dima=\pst@tempc\wd\pst@hbox
\ifdim\pst@dima<\z@\kern-\pst@dima\fi
\pst@Verb{CP CP translate \pst@tempa \tx@NET}%
\hbox to \z@{\box\pst@hbox\hss}%
\pst@Verb{%
CP CP translate
1 \pst@tempc div 1 \pst@tempd div scale
\tx@NET}%
\ifdim\pst@dima>\z@\kern\pst@dima\fi}}
\pslongbox{Scalebox}{\scalebox}
\def\scaleboxto(#1,#2){\pst@makebox{\@scaleboxto(#1,#2)}}
\def\@scaleboxto(#1,#2){%
\begingroup
\pssetlength\pst@dima{#1}%
\pssetlength\pst@dimb{#2}%
\ifdim\pst@dima=\z@\else
\pst@divide{\pst@dima}{\wd\pst@hbox}\pst@tempc
\edef\pst@tempc{\pst@tempc\space}%
\fi
\ifdim\pst@dimb=\z@
\ifdim\pst@dima=\z@
\@pstrickserr{%
\string\scaleboxto\space dimensions cannot both be zero}\@ehpa
\def\pst@tempa{}%
\def\pst@tempc{1 }%
\def\pst@tempd{1 }%
\else
\let\pst@tempd\pst@tempc
\fi
\else
\pst@dimc=\ht\pst@hbox
\advance\pst@dimc\dp\pst@hbox
\pst@divide{\pst@dimb}{\pst@dimc}\pst@tempd
\edef\pst@tempd{\pst@tempd\space}%
\ifdim\pst@dima=\z@ \let\pst@tempc\pst@tempd \fi
\fi
\edef\pst@tempa{\pst@tempc \pst@tempd scale }%
\@@scalebox
\endgroup}
\pslongbox{Scaleboxto}{\scaleboxto}
\def\tx@Rot{Rot }
\def\rotateleft{\pst@makebox{\@rotateleft\pst@hbox}}
\def\@rotateleft#1{%
\leavevmode\hbox{\hskip\ht#1\hskip\dp#1\vbox{\vskip\wd#1%
\pst@Verb{90 \tx@Rot}
\vbox to \z@{\vss\hbox to \z@{\box#1\hss}\vskip\z@}%
\pst@Verb{-90 \tx@Rot}}}}
\def\rotateright{\pst@makebox{\@rotateright\pst@hbox}}
\def\@rotateright#1{%
\hbox{\hskip\ht#1\hskip\dp#1\vbox{\vskip\wd#1%
\pst@Verb{-90 \tx@Rot}
\vbox to \z@{\hbox to \z@{\hss\box#1}\vss}%
\pst@Verb{90 \tx@Rot}}}}
\def\rotatedown{\pst@makebox{\@rotatedown\pst@hbox}}
\def\@rotatedown#1{%
\hbox{\hskip\wd#1\vbox{\vskip\ht#1\vskip\dp#1%
\pst@Verb{180 \tx@Rot}%
\vbox to \z@{\hbox to \z@{\box#1\hss}\vss}%
\pst@Verb{-180 \tx@Rot}}}}
\pslongbox{Rotateleft}{\rotateleft}
\pslongbox{Rotateright}{\rotateright}
\pslongbox{Rotatedown}{\rotatedown}
\def\pst@starbox{%
\setbox\pst@hbox\hbox{\psframebox*[boxsep=false]{\unhbox\pst@hbox}}}
\def\pst@@makesmall#1{%
\setbox#1=\hbox to\z@{\hss\vbox to \z@{\vss\box#1\vss}\hss}}
\def\pst@@@makesmall#1{%
\pst@dimh=\psk@xref\wd#1%
\ifx\psk@yref\relax
\pst@dimg=\dp#1%
\else
\pst@dimg=\psk@yref\ht#1%
\advance\pst@dimg\psk@yref\dp#1%
\fi
\setbox#1=\hbox to\z@{%
\kern-\pst@dimh\vbox to\z@{\vss\box#1\kern-\pst@dimg}\hss}}
\def\psset@ref#1{\pst@expandafter\psset@@ref{#1}\@empty,,\@nil}
\def\psset@@ref#1#2,#3,#4\@nil{%
\def\psk@xref{.5}%
\def\psk@yref{.5}%
\let\pst@makesmall\pst@@@makesmall
\ifx\@empty#3\@empty
\@nameuse{getref@#1}%
\@nameuse{getref@#2}%
\else
\pst@checknum{#1#2}\psk@xref
\pst@checknum{#3}\psk@yref
\fi}
\def\getref@c{\let\pst@makesmall\pst@@makesmall}
\def\getref@t{\def\psk@yref{1}}
\def\getref@b{\def\psk@yref{0}}
\def\getref@B{\let\psk@yref\relax}
\def\getref@l{\def\psk@xref{0}}
\def\getref@r{\def\psk@xref{1}}
\psset@ref{c}
\def\psset@rot#1{%
\pst@expandafter{\@ifnextchar*{\psset@@@rot}{\psset@@rot}}{#1}\@nil}
\def\psset@@rot#1\@nil{%
\def\next##1@#1=##2@##3\@nil{%
\ifx\relax##2%
\pst@getangle{#1}\psk@rot
\else
\def\psk@rot{##2}%
\fi}%
\expandafter\next\pst@rottable @#1=\relax @\@nil}
\def\psset@@@rot#1#2\@nil{%
\psset@@rot#2\@nil
\edef\psk@rot{\pst@rotlist \ifx\psk@rot\@empty\else\psk@rot add \fi}}
\def\pst@rotlist{mark RAngle /a ED cleartomark a neg }
\def\pst@rottable{%
@0=%
@U=%
@L=90 %
@D=180 %
@R=-90 %
@N=\pst@rotlist
@W=\pst@rotlist 90 add %
@S=\pst@rotlist 180 add %
@E=\pst@rotlist 90 sub }
\psset@rot{0}
\def\tx@RotBegin{RotBegin }
\def\tx@RotEnd{RotEnd }
\def\pst@rotate#1#2{%
\ifx#1\@empty\else
\setbox#2=\hbox{\pst@Verb{#1 \tx@RotBegin}\box#2\pst@Verb{\tx@RotEnd}}%
\fi}
\def\psput@cartesian#1{%
\hbox to \z@{\kern\pst@dimg{\vbox to \z@{\vss\box#1\vskip\pst@dimh}\hss}}}
\def\psput@special#1{%
\hbox{%
\pst@Verb{{ \pst@coor } \tx@PutCoor \tx@PutBegin}%
\box#1%
\pst@Verb{\tx@PutEnd}}}
\def\tx@PutCoor{PutCoor }
\def\tx@PutBegin{PutBegin }
\def\tx@PutEnd{PutEnd }
\def\rput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\rput@i}{\rput@ii}}}
\def\rput@i[#1]{\addto@par{ref={#1}}\rput@ii}
\def\rput@ii{\@ifnextchar({\rput@iv}{\rput@iii}}
\def\rput@iii#1{\addto@par{rot={#1}}\@ifnextchar({\rput@iv}{\rput@iv(\z@,\z@)}}
\def\rput@iv(#1){\pst@killglue\pst@makebox{\rput@v{#1}}}
\def\rput@v#1{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\pst@makesmall\pst@hbox
\pst@rotate\psk@rot\pst@hbox
\psput@{#1}\pst@hbox
\endgroup
\ignorespaces}
\def\multirput{%
\def\pst@par{}%
\pst@ifstar{\@ifnextchar[{\multirput@i}{\multirput@ii}}}
\def\multirput@i[#1]{\addto@par{ref={#1}}\multirput@ii}
\def\multirput@ii{\@ifnextchar({\multirput@iv}{\multirput@iii}}
\def\multirput@iii#1{\addto@par{rot={#1}}\multirput@iv}
\def\multirput@iv(#1){%
\@ifnextchar({\multirput@v(#1)}{\multirput@v(\z@,\z@)(#1)}}
\def\multirput@v(#1,#2)(#3,#4)#5{%
\pst@makebox{\multirput@vi(#1,#2)(#3,#4){#5}}}
\def\multirput@vi(#1,#2)(#3,#4)#5{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\pst@makesmall\pst@hbox
\pst@rotate\psk@rot\pst@hbox
\pssetxlength\pst@dima{#1}%
\pssetylength\pst@dimb{#2}%
\pssetxlength\pst@dimc{#3}%
\pssetylength\pst@dimd{#4}%
\pst@cntg=#5\relax
\pst@cnth=\@ne
\leavevmode
\loop
\vbox to \z@{%
\vss
\hbox to \z@{\kern\pst@dima\copy\pst@hbox\hss}%
\vskip\pst@dimb}%
\ifnum\pst@cntg>\pst@cnth
\advance\pst@dima\pst@dimc
\advance\pst@dimb\pst@dimd
\advance\pst@cnth\@ne
\repeat
\endgroup
\ignorespaces}
\newif\if@fixedradius
\def\cput{\pst@object{cput}}
\def\cput@i{\@fixedradiusfalse\cput@ii}
\def\cput@ii{\pst@killglue\@ifnextchar({\cput@iv}{\cput@iii}}
\def\cput@iii#1{%
\addto@par{rot={#1}}%
\@ifnextchar({\cput@iv}{\cput@iv(\z@,\z@)}}
\def\cput@iv(#1){\pst@makebox{\cput@v{#1}}}
\def\cput@v#1{%
\begingroup
\use@par
\setbox\pst@hbox=\hbox{%
\psboxsepfalse
\if@fixedradius\psCirclebox@ii\else\pscirclebox@ii\fi}%
\pst@@makesmall\pst@hbox
\pst@rotate\psk@rot\pst@hbox
\psput@{#1}\pst@hbox
\endgroup
\ignorespaces}
\def\Cput{\pst@object{Cput}}
\def\Cput@i{\@fixedradiustrue\cput@ii}
\newdimen\pslabelsep
\def\psset@labelsep#1{\pssetlength\pslabelsep{#1}}
\psset@labelsep{5pt}
\def\psset@refangle#1{\pst@expandafter\psset@@refangle{#1}\@nil}
\def\psset@@refangle#1\@nil{%
\def\next##1@#1=##2"##3@##4\@nil{%
\ifx\relax##2%
\pst@getangle{#1}\psk@refangle
\def\psk@uputref{}%
\else
\def\psk@refangle{##2 }%
\def\psk@uputref{##3}%
\fi}%
\expandafter\next\pst@refangletable @#1=\relax"@\@nil}
\def\pst@refangletable{%
@r=0"20%
@u=90"02%
@l=180"10%
@d=-90"01%
@ur=45"22%
@ul=135"12%
@dr=-135"21%
@dl=-45"11}
\psset@refangle{0}
% DG/SR modification begin - Mar. 24, 1999 - Patch 10
%\def\uput{\def\pst@par{}\@ifnextchar[{\uput@ii}{\uput@i}}
\def\uput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\uput@ii}{\uput@i}}} 
% DG/SR modification end
\def\uput@i#1{\addto@par{labelsep=#1}\uput@ii}
\def\uput@ii[#1]{%
\addto@par{refangle={#1}}%
\@ifnextchar({\uput@iv}{\uput@iii}}
\def\uput@iii#1{%
\addto@par{rot={#1}}%
\@ifnextchar({\uput@iv}{\uput@iv(\z@,\z@)}}
\def\uput@iv(#1){\pst@killglue\pst@makebox{\uput@v{#1}}}
\def\uput@v#1{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\uput@vi
\psput@{#1}\pst@hbox
\endgroup
\ignorespaces}
\def\uput@vi{%
\ifx\psk@uputref\@empty
\uput@vii\tx@UUput{}%
\else
\ifx\psk@rot\@empty
\expandafter\uput@viii\psk@uputref
\else
\uput@vii\tx@UUput{}%
\fi
\fi}
\def\uput@vii#1#2{%
\edef\pst@coor{%
\pst@number\pslabelsep
#2%
\pst@number{\wd\pst@hbox}%
\pst@number{\ht\pst@hbox}%
\pst@number{\dp\pst@hbox}%
\psk@refangle\space \ifx\psk@rot\@empty\else\psk@rot\space sub \fi
\tx@Uput #1}%
\setbox\pst@hbox=\hbox to\z@{\hss\vbox to\z@{\vss\box\pst@hbox\vss}\hss}%
\setbox\pst@hbox=\psput@special\pst@hbox
\ifx\psk@rot\@empty\else\pst@rotate\psk@rot\pst@hbox\fi}
\def\uput@viii#1#2{%
\ifnum#1>\z@\ifnum#2>\z@\pslabelsep=.707\pslabelsep\fi\fi
\setbox\pst@hbox=\vbox to\z@{%
\ifnum#2=1 \vskip\pslabelsep\else\vss\fi
\hbox to\z@{%
\ifnum#1=2 \hskip\pslabelsep\else\hss\fi
\box\pst@hbox
\ifnum#1=1 \hskip\pslabelsep\else\hss\fi}%
\ifnum#2=2 \vskip\pslabelsep\else\vss\fi}}
\def\tx@Uput{Uput }
\def\tx@UUput{UUput }
\def\Rput{\def\pst@par{}\pst@ifstar{\@ifnextchar[{\Rput@ii}{\Rput@i}}}
\def\Rput@i#1{\addto@par{labelsep=#1}\Rput@ii}
\def\Rput@ii[#1]{\addto@par{ref={#1}}\@ifnextchar({\Rput@iv}{\Rput@iii}}
\def\Rput@iii#1{\addto@par{rot={#1}}\@ifnextchar({\Rput@iv}{\Rput@iv(\z@,\z@)}}
\def\Rput@iv(#1){\pst@killglue\pst@makebox{\Rput@v{#1}}}
\def\Rput@v#1{%
\begingroup
\use@par
\if@star\pst@starbox\fi
\Rput@vi
\pst@makesmall\pst@hbox
\pst@rotate\psk@rot\pst@hbox
\psput@{#1}\pst@hbox
\endgroup
\ignorespaces}
\def\Rput@vi{%
\pst@dimg=\dp\pst@hbox
\advance\pst@dimg\pslabelsep
\dp\pst@hbox=\pst@dimg
\pst@dimg=\ht\pst@hbox
\advance\pst@dimg\pslabelsep
\ht\pst@hbox=\pst@dimg
\setbox\pst@hbox\hbox{\kern\pslabelsep\box\pst@hbox\kern\pslabelsep}}%
\def\oldpsput{%
\def\pst@par{}\pst@ifstar{\@ifnextchar[{\oldpsput@i}{\oldpsput@ii}}}
\def\oldpsput@i[#1]{\addto@par{ref={#1}}\oldpsput@ii}
\def\oldpsput@ii{\@ifnextchar<{\oldpsput@iii}{\oldpsput@iv}}
\def\oldpsput@iii<#1>{\rput@iii{#1}}
\def\OldPsput{\let\psput\oldpsput}
\def\NewPsput{\let\psput\rput}
\def\pspicture{\begingroup\pst@ifstar\pst@picture}
\def\pst@picture{%
\@ifnextchar[{\pst@@picture}{\pst@@picture[0]}}
\def\pst@@picture[#1]#2(#3,#4){%
\@ifnextchar({\pst@@@picture[#1](#3,#4)}%
{\pst@@@picture[#1](0,0)(#3,#4)}}
\def\pst@@@picture[#1](#2,#3)(#4,#5){%
\pssetxlength\pst@dima{#2}%
\pssetylength\pst@dimb{#3}%
\pssetxlength\pst@dimc{#4}%
\pssetylength\pst@dimd{#5}%
\ifdim\pst@dima>\pst@dimc
\pst@dimg=\pst@dima
\pst@dima=\pst@dimc
\pst@dimc=\pst@dimg
\fi
\ifdim\pst@dimb>\pst@dimd
\pst@dimg=\pst@dimb
\pst@dimb=\pst@dimd
\pst@dimd=\pst@dimg
\fi
\def\pst@tempa{#1}%
\setbox\pst@hbox=\hbox\bgroup
\begingroup\KillGlue
\@ifundefined{@latexerr}{}{\let\unitlength\psunit}%
\edef\pic@coor{(#2,#3)(#2,#3)(#4,#5)}\ignorespaces}
\def\pic@coor{(0,0)(0,0)(10,10)}
\def\endpspicture{%
\pst@killglue
\endgroup
\egroup
\ifdim\wd\pst@hbox=\z@\else
%\@pstrickserr{Extraneous space in the pspicture environment}%
%{Type \space <return> \space to procede.}%
\fi
\ht\pst@hbox=\pst@dimd
\dp\pst@hbox=-\pst@dimb
\setbox\pst@hbox=\hbox{%
\kern-\pst@dima
\ifx\pst@tempa\@empty\else
\advance\pst@dimd-\pst@dimb
\pst@dimd=\pst@tempa\pst@dimd
\advance\pst@dimd\pst@dimb
\lower\pst@dimd
\fi
\box\pst@hbox
\kern\pst@dimc}%
\if@star\setbox\pst@hbox=\hbox{\clipbox@@\z@}\fi
\leavevmode\box\pst@hbox
\endgroup}
\@namedef{pspicture*}{\pspicture*}
\@namedef{endpspicture*}{\endpspicture}
\def\tx@BeginOL{BeginOL }
\def\tx@InitOL{InitOL }
\def\pst@initoverlay#1{\pst@Verb{\tx@InitOL /TheOL (#1) def}}
\def\AltOverlayMode{%
\def\pst@initoverlay##1{%
\pst@Verb{%
\tx@InitOL
/Visible { initclip } def
/Invisible {
CP newpath OLUnit itransform moveto clip newpath moveto
} def
/TheOL (##1) def}}}
\def\pst@overlay#1{%
\edef\curr@overlay{#1}%
\pst@Verb{(#1) BOL}%
\aftergroup\pst@endoverlay}
\def\pst@endoverlay{%
\pst@Verb{(\curr@overlay) BOL}}
\def\curr@overlay{all}
\newbox\theoverlaybox
\def\overlaybox{%
\global\setbox\theoverlaybox=\hbox\bgroup
\begingroup
\let\psoverlay\pst@overlay
\def\overlaybox{%
\@pstrickserr{Overlays cannot be nested}\@eha}%
\def\putoverlaybox{%
\@pstrickserr{You must end the overlay box
before using \string\putoverlaybox}}%
\psoverlay{main}%
\ignorespaces}
\def\endoverlaybox{\endgroup\egroup}
\def\putoverlaybox#1{%
\hbox{\pst@initoverlay{#1}\copy\theoverlaybox}}
\def\psoverlay{\@pstrickserr{\string\psoverlay\space
can only be used after \string\overlaybox}}
\ifx\pstcustomize\relax \input pstricks.con \fi
\catcode`\@=\PstAtCode\relax
%
\endinput
%%
%% END: pstricks.tex

cs0207049.extracted_bib
\begin{thebibliography}{10}

\bibitem{set-based-popl}
W.~Charatonik, A.~Podelski, and J.-M. Talbot.
\newblock {P}aths vs. {T}ress in {S}et-based {P}rogram {A}nalysis.
%\newblock In {\em Principles of Programming Languages}, pages 330--338. {ACM}
\newblock In {\em POPL00}, pages 330--338. {ACM}
  {P}ress, January 2000.

\bibitem{LeCharlier94:toplas}
B.~Le Charlier and P.~{Van Hentenryck}.
\newblock {E}xperimental {E}valuation of a {G}eneric {A}bstract
  {I}nterpretation {A}lgorithm for {P}rolog.
\newblock {\em ACM Transactions on Programming Languages and Systems},
  16(1):35--101, 1994.

\bibitem{Dart-Zobel}
P.W. Dart and J.~Zobel.
\newblock {A} {R}egular {T}ype {L}anguage for {L}ogic {P}rograms.
\newblock In F.~Pfenning, editor, {\em {T}ypes in {L}ogic {P}rogramming}, pages
  157--187. MIT Press, 1992.

\bibitem{FruewirthShapiroVardiYardeni91}
T.~Fr{\"u}wirth, E.~Shapiro, M.Y. Vardi, and E.~Yardeni.
\newblock Logic programs as types for logic programs.
\newblock In {\em Proc. LICS'91}, pages 300--309, 1991.

\bibitem{gallagher-types-iclp94}
J.P. Gallagher and D.A. de~Waal.
\newblock Fast and precise regular approximations of logic programs.
\newblock In Pascal {Van~Hentenryck}, editor, {\em Proc.~of the 11th
  International Conference on Logic Programming}, pages 599--613. MIT Press,
  1994.

\bibitem{ciaopp-iclp99-tut}
M.~Hermenegildo, F.~Bueno, G.~Puebla, and P.~L\'{o}pez-Garc\'{\i}a.
\newblock {P}rogram {A}nalysis, {De}bugging and {O}ptimization {U}sing the
  {C}iao {S}ystem {P}reprocessor.
%\newblock In {\em 1999 International Conference on Logic Programming}, pages
\newblock In {\em ICLP99}, pages
  52--66, Cambridge, MA, November 1999. MIT Press.

\bibitem{janss92}
G.~Janssens and M.~Bruynooghe.
\newblock Deriving {D}escriptions of {P}ossible {V}alues of {P}rogram
  {V}ariables by means of {A}bstract {I}nterpretation.
\newblock {\em Journal of Logic Programming}, 13(2 and 3):205--258, July 1992.

\bibitem{lindgrenmildner}
T.~Lindgren and P.~Mildner.
\newblock The impact of structure analysis on prolog compilation.
\newblock Tech.\ Rep.\ 140, Computing Science Dept., Uppsala
  University, 1997.

\bibitem{mildnerthesis}
P.~Mildner.
\newblock {\em Type Domains for Abstract Interpretation: A Critical Study}.
\newblock PhD thesis, Computing Science Department - Uppsala University, 1999.

\bibitem{Saglam-Gallagher-94}
H.~Saglam and J.~Gallagher.
\newblock Approximating logic programs using types and regular descriptions.
\newblock Tech.\ Rep.\ CSTR-94-19, Dept.\ of C.\ Science,
  U.\ of Bristol, 1994.

\bibitem{VanHentenryckCortesiLeCharlier95}
P.~Van~Hentenryck, A.~Cortesi, and B.~Le~Charlier.
\newblock Type analysis of prolog using type graphs.
\newblock {\em Journal of Logic Programming}, 22(3):179--209, 1995.

\end{thebibliography}