\documentclass{report}

\usepackage{latexsym}
\usepackage[dvips]{graphics}
\pagestyle{headings}
%%\usepackage{fullpage}

%% $Header: /cs/wilmesj/public/cvsroot/counters/counters.w,v 1.77 1998/12/03 18:30:16 wilmesj Exp $

\title{Operation Counting Adaptors for STL}
% alphabetical order; how convenient for me
\author{Gillmer J. Derge, Markus Kuhn, Josh Wilmes\\
\textit{$\{$dergeg,kuhnm,wilmesj$\}$@@rpi.edu}
}

\begin{document}
\maketitle
\tableofcontents

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
Algorithms are often analyzed in terms of their complexity, which is
frequently defined in terms of execution time.  In generic
programming, however, discussions of time requirements are not always
practical, since the time needed to perform an operation on one data
type may vary quite a bit from that required for another.  One way to
obtain a more useful complexity measure for generic algorithms is to
think in terms of the abstract operations performed on the data.
Thus, for example, a sort algorithm could be measured by the number of
comparisons and assignments it performs.
This report presents a number of adaptors for the
C\textsuperscript{++} Standard Template Library (STL) that allow the
programmer to count the operations done on data types.  The classes
also provide a rich set of reporting and data analysis functions. 

\vspace{4.5in}
%%\rule{\textwidth}{.5pt}\\
\verb|$Revision: 1.77 $ ($Date: 1998/12/03 18:30:16 $)|
\end{abstract}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{User's Guide}

\section{Introduction}

When evaluating algorithms, generic algorithms in particular, it can
be useful to have a measure of the operations performed by the
algorithms.  For example, one of the differences between a typical
Quicksort versus a heap sort is that the heap sort performs fewer
comparisons but more assignments.  Although the general rule of thumb
is that Quicksort is more efficient than heap sort, if comparisons are
relatively expensive computationally compared to assignments, then the
Quicksort might be less desirable for that particular application.

If it were easy to obtain counts of operations, it would be far easier
to trade off the relative advantages and disadvantages of different
algorithms.  The library presented in this report provides just such a
facility.

The library implements a set of ``counting adaptors.''  These adaptors
redefine the operations that are supported by a type to increment a
counter and then defer to the base operation.  For example, an adapted
\verb|int| would support an addition operator which would increment a
count of additions and then perform a normal \verb|int| addition.

There are adaptors for each of the data types typically used by STL
algorithms: iterators, container value types, container difference
types and functors.  Additionally there is a \verb|recorder| class
that provides for both data analysis and control over the counting
process.

\section{Counting Adaptors}

The general approach to analyzing the algorithm of a function
\verb|f()| is to adapt each argument of \verb|f()| with a counting
type.  Then all of the work \verb|f()| does on its arguments will be
recorded.  Additionally any \verb|Container| used by the algorithm
(either directly or via iterators) should be modified to contain
counting elements.  This is better illustrated by a simple example.

Suppose it was desired to analyze the computational requirements of
the STL sort algorithm.  A non-counting call to sort a vector of
integers might look as shown below.

@d non-counting sort example 
@{vector<int> v;
// initialize v
sort(v.begin(), v.end());
@}

In order to count the operations done by \verb|sort()| two changes are
made.  First the vector is changed to be a vector of counting
integers.  Second the iterators passed to sort are made to be counting
iterators.

@d counting sort example 
@{vector<value_counter<int> > v;
typedef vector<value_counter<int> > V;
// initialize v
sort(iterator_counter<V::iterator>(v.begin()), 
     iterator_counter<V::iterator>(v.end()));
@}

Now all of the operations performed on the iterators and their values
will be counted.  In fact, any operations performed on the
\verb|difference_type| of the iterators will also be counted.  The
counting iterators automatically use a counting
\verb|difference_type|.

There are five adaptor types that would typically be relevant to a
library user and a sixth that is generally used only internally.

\begin{itemize}
\item \verb|iterator_counter| adapts STL iterators
\item \verb|value_counter| adapts the \verb|value_type| of STL \verb|Containers|
\item \verb|generator_counter| adapts generator functors
\item \verb|unary_function_counter| adapts unary functors
\item \verb|binary_function_counter| adapts binary functors
\end{itemize}

The sixth type, \verb|difference_counter| adapts the
\verb|difference_type| of iterators and as mentioned above, is not
typically useful outside the library's internals.

An example using a \verb|binary_function_counter| is shown below.

@d counting sort example, with binary function 
@{vector<value_counter<int> > v;
typedef vector<value_counter<int> > V;
// initialize v
less<int> compare;
sort(iterator_counter<V::iterator>(v.begin()), 
     iterator_counter<V::iterator>(v.end()),
     binary_function_counter<less<int> >(compare));
@}

\section{Recording Results}

Access to the operation counts is done via the \verb|recorder| class.
Objects of type \verb|recorder| save snapshots of values of the
counters.  These can then be reported and analyzed statistically.

A typical approach to using the adaptors would be to run the algorithm
several times, collecting a statistical sample of the performance.
This can be done using the \verb|recorder| class as shown below.

@d \verb|recorder| example 
@{recorder<> r;
for (int i = 0; i < niterations; ++i) {
  // invoke algorithm
  r.record();
}
@}

The \verb|record()| method both saves the current values of the
counters and resets them to zero.  The values may also be reset
independently by calling the \verb|reset()| method.

Often in addition to calling the algorithm itself, the loop will
perform some setup steps to prepare the test data.  For example, to
test a sort algorithm one would likely create a randomized sequence of
data.  Since these setup operations will be working with counting
types, the setup work will also be shown in the results.  This should
be prevented, since it will bias the analysis.

To this end, it is possible to pause and resume counting via a
\verb|recorder| object.  The code below shows a modified version of
the previous example that includes setup operations.  Any processing
done between the pause and resume will not be reflected in the
counting results.

@d \verb|recorder| pause/resume example 
@{recorder<> r;
for (int i = 0; i < niterations; ++i) {
  r.pause(); {
    // setup test data
  } r.resume();

  // invoke algorithm
  r.record();
}
@}

Since it is important to match a call to \verb|pause()| with a
corresponding call to \verb|resume()| it is a useful idiom to create a
nested block of code with braces ($\{\}$) as shown above as a visual
cue indicating the statements whose operations will not be counted.

\section{Reporting and Analyzing Results}

As discussed in the previous section, after the analysis is completed,
the
% forced line-break due to overfull hbox
\\\verb|recorder| will contain a statistical sample of counts from
different trials of the algorithm.  One will normally want to report
some statistical property of that sample --- perhaps median, mean,
minimum or maximum.  By default the \verb|recorder| will report the
median of the trials via its output operator, since that statistic is
less sensitive to outliers.

@d \verb|recorder| output example 1 
@{cout << r;  // report median
@}

It is also possible to show the minimum or maximum.

@d \verb|recorder| output example 2 
@{r.show_median_counts(false);
r.show_min_counts(true);
r.show_max_counts(true);
cout << r;  // report min and max but not median
@}

The Reference Manual describes ways in which to get more advanced and
generalized reporting features.

Under normal use the operation counts for each category of adaptor are
reported separately and as an overall total.  Thus, there will be
listings for \verb|iterator_counter| operations, \verb|value_counter|
operations,
% forced line-break due to overfull hbox
\\\verb|difference_counter| operations, etc. along with the total.

Occasionally it may be useful to obtain counts at a finer level of
granularity.  For example, it may be important to distinguish between
operations on vector iterators versus list iterators.  In this case it
is possible to supply a name to the counting adaptor which will be
used in reporting.  This name must be an external identifier.

@d \verb|iterator_counter| name example 
@{char name1[] = "list<int>::iterator";
char name2[] = "vector<int>::iterator";

typedef iterator_counter<list<int>::iterator, name1> iterator1;
typedef iterator_counter<vector<int>::iterator, name2> iterator2;
@}

In the above example, any operations performed on \verb|iterator1| or
\verb|iterator2| will be reported separately from other
\verb|iterator_counter| types.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Reference Manual}

\section{Recorder}

The \verb|recorder| provides several functions to control its
recording of counters:

\begin{itemize}
\item{\verb|void pause()|} pauses all recording until resume() is called.

\item{\verb|void resume()|} resumes recording.

\item{\verb|void record()|} records all current counts as an iteration
and calls \verb|reset()| to begin a new iteration.

\item{\verb|void reset()|} begins a new iteration by clearing the
recorded counts.

\item{\verb|void insert(string, counter_vector*)|} adds a
\verb|counter_vector| to the \verb|recorder|'s global registry, so
that its counts will be recorded.  This funciton should not need be
called explicitly, because \verb|counter_vector|'s constructor calls
it automatically. 

\end{itemize}

\subsection{Evaluators}

A number of functions are provided to customize the behavior of the
\verb|recorder| output operator.\\

% forced new page for prettiness.
\newpage

\begin{itemize}

\item{\bf Operator Masking Functions}\\
The following functions allow the user to show or hide particular
counted operations in the report output.

\small
\begin{tabular}{|l|l|l|l|}
\hline
Function                      & Default &  Description                   &  Example \\
\hline
\verb|show_all_ops()|         &  on     &  Show All Operators         & \verb|r.show_all_ops();|\\
\verb|hide_no_ops()|          &         &                             & \verb|r.hide_no_ops();|\\
\hline
\verb|hide_all_ops()|         &  off    &  Hide All Operators         & \verb|r.show_all_ops();|\\
\verb|show_no_ops()|          &         &                             & \verb|r.show_no_ops();|\\
\hline
\verb|show_op(operator_type)| &   n/a   &  Show a Particular Operator & \verb|r.show_op(r.PLUS_CTOR);|\\
\hline
\verb|hide_op(operator_type)| &   n/a   &  Hide a Particular Operator & \verb|r.hide_op(r.PLUS_CTOR);|\\
\hline
\verb|show_op(operator_type,| &   n/a   &  Show/Hide Particular Ops   & \verb|r.show_op(r.PLUS,true);|\\
\verb|        bool)         | &         &                             & \\
\hline
\verb|show_op(InputIterator,| &   n/a   &  Show/Hide Group of Ops     & \verb|vector<bool> o = (true,false);|\\
\verb|        InputIterator)| &         &                             & \verb|r.show_op(o.begin(),o.end());|\\
\hline
\end{tabular}
\normalsize

\item{\bf Snapshot Presentation Options}\\
The default is to show the median count for each operation across all
snapshots.

\begin{tabular}{|l|l|l|}
\hline
Function                      & Default & Description\\
\hline
\verb|show_min_counts(bool)|    & false   & Include Minimum Counts\\
\verb|show_min_counts()    |    &         &\\
\hline
\verb|show_max_counts(bool)|    & false   & Include Maximum Counts\\
\verb|show_max_counts()    |    &         &\\
\hline
%% not implemented
%\verb|show_mean_counts(bool)|   & false   & Include Mean Counts \\
%\verb|show_mean_counts()    |   &         &\\
%\hline
\verb|show_median_counts(bool)| & true    & Include Median Counts\\
\verb|show_median_counts()    | &         &\\
\hline
%% not implemented
%\verb|show_all_counts(bool)|    & false   & Include All Counts\\
%\verb|show_all_counts()    |    &         &\\
%\hline
\verb|show_zero_counts(bool)|   & false   & Include Zero Counts\\
\verb|show_zero_counts()    |   &         &\\
\hline
\end{tabular}

\end{itemize}

\section{iterator\_counter\small{$<$Iterator,Difference,Name,Counter$>$}}

\subsection{Description}

\verb|iterator_counter| is an iterator adaptor that counts how often each 
method of an iterator is called.  Like all counting adaptors, the
counts are stored in a \verb|counter_vector| and recorded by the
\verb|recorder| after each iteration.   With this adaptor all
iterators can be adapted. 

\subsection{Example of use}

@D \verb|iterator_counter| example of use
@{
  typedef vector<int> int_vector;

  typedef iterator_counter<int_vector::iterator>
             counted_vector_iterator;

  recorder<> r;
  int_vector v;

  for (int i = 0; i < 5; i++) {
    v.push_back(i+100);
  }

  // external constructor
  counted_vector_iterator iter1(v.begin());

  // copy constructor
  counted_vector_iterator iter2 = iter1;

  //preincrement
  ++iter1;

  r.record();
  cout << r;
@}
In this example, one external constructor, one copy constructor, and one
preincrement is counted.

\subsection{Definition}
Defined in \verb|counters.h|

\subsection{Template parameters}
\small{
\begin{tabular}{|l|l|l|}                                                              \hline
Parameter   & Description                     & Default                            \\ \hline
Iterator    & The base iterator class. All    &                                    \\ 
            & Operation on this class are     &                                    \\
            & counted.                        &                                    \\ \hline
Difference  & The difference type, which is   & \verb|difference_counter<typename| \\
            & normally the adapted difference & \verb|iterator_traits<Iterator>::| \\
            & of the base class.              & \verb|difference_type,  Iterator>| \\ \hline
Name        & The Name, which is used for     & null                               \\
            & the recorder. If it is null,    &                                    \\
            & "\verb|iterator_counter|" is used. &                                 \\ \hline
Counter     & The type which is used for the  & unsigned long                      \\ 
            & counting.                       &                                    \\ \hline
\end{tabular}
}
\subsection{Model of}
Random Access Iterator

\subsection{Type requirements}

The base iterator type (that is, the template parameter Iterator) must
be a Random Access Iterator or an Iterator, which implement a subset
of the Random Access Iterator. As an consequence, each STL Iterator
can be adapted.  The \verb|Difference| type is normally the
\verb|difference_type| of the base iterator adapted by
\verb|difference_counter|.

\subsection{Public base classes}
None.

\subsection{Members}
\small{
\begin{tabular}{|l|l|l|}                                                                         \hline
Member                                   & Where Defined           & Description              \\ \hline
\verb|iterator_counter()|                & Default Constructible   & The default              \\
                                         &                         & constructor              \\ \hline
\verb|iterator_counter|                  & Assignable              & The copy                 \\
\verb|    (const iterator_counter& x)|   &                         & constructor              \\ \hline
\verb|iterator_counter& operator=|       & Assignable              & The assignment           \\ 
\verb|    (const iterator_counter& y)|   &                         & operator                 \\ \hline
\verb|iterator_counter|                  & \verb|iterator_counter| & see below                \\
\verb|    (const Iterator& x) |          &                         &                          \\ \hline
\verb|Iterator base()|                   & \verb|iterator_counter| & see below                \\ \hline
\verb|bool operator==|                   & Equality Comparable     & Compares two             \\        
\verb|    (const iterator_counter& x|    &                         & iterators for            \\ 
\verb|     const iterator_counter& y)|   &                         & equality.                \\ \hline
\verb|bool operator<|                    & LessThan Comparable     & Determines whether       \\
\verb|    (const iterator_counter& x,|   &                         & the first  argument      \\
\verb|     const iterator_counter& y)|   &                         & precedes the second.     \\ \hline
\verb|reference operator* ()|            & Trivial Iterator        & The dereference          \\ 
                                         &                         & operator                 \\ \hline
\verb|iterator_counter& operator++ ()|   & Forward Iterator        & Preincrement             \\ \hline
\verb|iterator_counter operator++ (int)| & Forward Iterator        & Postincrement            \\ \hline
\verb|iterator_counter& operator-- ()|   & Bidirectional Iterator  & Predecrement             \\ \hline
\verb|iterator_counter operator-- (int)| & Bidirectional Iterator  & Postdecrement            \\ \hline
\verb|iterator_counter operator+|        & Random Access Iterator  & Iterator addition        \\
\verb|    (const Difference& n)|         &                         &                          \\ \hline
\verb|iterator_counter operator+|        & Random Access Iterator  & Iterator addition        \\
\verb|    (const Difference& n,|         &                         &                          \\
\verb|     const iterator_counter& n)|   &                         &                          \\ \hline
\verb|iterator_counter& operator+=|      & Random Access Iterator  & Iterator addition        \\
\verb|    (const Difference& n)|         &                         &                          \\ \hline
\verb|iterator_counter operator-|        & Random Access Iterator  & Iterator subtraction     \\
\verb|    (const Difference& n)|         &                         &                          \\ \hline
\verb|Difference operator-|              & Random Access Iterator  & Iterator subtraction     \\
\verb|    (const iterator_counter& i)|   &                         &                          \\ \hline
\verb|iterator_counter& operator-=|      & Random Access Iterator  & Iterator subtraction     \\
\verb|    (const Difference& y)|         &                         &                          \\ \hline
\verb|reference operator[]|              & Random Access Iterator  & Random access to an      \\
\verb|    (const Difference& n)|         &                         & element.                 \\ \hline
\end{tabular}
}
\subsection{New Members}
These members are not defined in the Random Access Iterator requirements, but are specific to 
\verb|iterator_counter|.\\

\small{
\begin{tabular}{|l|l|}                                                                  \hline
Member                         & Description                                          \\ \hline
\verb|iterator_counter|        & This constructor takes the object n of the base      \\
\verb|    (const Iterator& n)| & class and create an \verb|iterator_counter| with it. \\ \hline
\verb|Iterator base()|         & Returns the current value of the                     \\
                               & \verb|iterator_counter|'s base iterator.             \\ \hline
\end{tabular}
\subsection{Notes}
None.

\section{difference\_counter\small{$<$Difference,Iterator,Name,Counter$>$}}

\subsection{Description}

\verb|difference_counter| is an adaptor around a
\verb|difference_type| from an iterator.  It counts how often each
method of the \verb|difference_type| is called.  Like all counting
adaptors, the counts are stored in a \verb|counter_vector| and
recorded by the \verb|recorder| after each iteration.  

\subsection{Example of use}

@D \verb|difference_counter| example of use 
@{  typedef vector<int> int_vector;

  typedef difference_counter<int_vector::difference_type,
                             int_vector::iterator>
             counted_vector_difference;

  recorder<> r;
  int_vector v;

  for (int i = 0; i < 5; i++) {
    v.push_back(i+100);
  }

  // external constructor
  counted_vector_difference diff1(v.end() - v.begin());

  // copy constructor
  counted_vector_difference diff2 = diff1;

  //preincrement
  ++diff1;

  r.record();
  cout << r;
@}
In this example, one external constructor, one copy constructor, and one
preincrement is counted.

\subsection{Definition}
Defined in \verb|counters.h|

\subsection{Template parameters}
\small{
\begin{tabular}{|l|l|l|}                                                                             \hline
Parameter       & Description                                & Default                            \\ \hline
Difference      & The base difference, which is normally     &                                    \\ \hline
Iterator        & The base iterator class of which this is   &                                    \\
                & the difference.                            &                                    \\ \hline
Name            & The Name, which is used for the recorder.  & null                               \\
                & If it is null, "\verb|difference_counter|" is used. &                           \\ \hline
Counter         & The type which is used for the counting.   & unsigned long                      \\ \hline
\end{tabular}
}
\subsection{Model of}
Assignable, Default Constructible, Equality Comparable, LessThan Comparable

\subsection{Type requirements}
The base difference type (that is, the template parameter Difference) must be a Difference of an
Iterator. The Iterator has to be the corresponding Iterator.

\subsection{Public base classes}
None.

\subsection{Members}
\small{
\begin{tabular}{|l|l|l|}                                                                            \hline
Member                                     & Where Defined             & Description             \\ \hline
\verb|difference_counter()|                & Default Constructible     & The default constructor \\ \hline
\verb|difference_counter|                  & Assignable                & The copy constructor    \\
\verb|   (const difference_counter& x)|    &                           &                         \\ \hline
\verb|difference_counter& operator=|       & Assignable                & The assignment operator \\ 
\verb|   (const difference_counter& y)|    &                           &                         \\ \hline
\verb|difference_counter|                  & \verb|difference_counter| & see below               \\ \hline
\verb|   (const Difference& x)|            &                           &                         \\
\verb|Difference base()|                   & \verb|difference_counter| & see below               \\ \hline
\verb|operator int()|                      & \verb|difference_counter| & see below               \\ \hline
\verb|bool operator==|                     & Equality Comparable       & Compares two iterators  \\        
\verb|   (const difference_counter& x|     &                           & for equality.           \\ 
\verb|    const difference_counter& y)|    &                           &                         \\ \hline
\verb|bool operator<|                      & LessThan Comparable       & Determines whether the  \\
\verb|   (const difference_counter& x,|    &                           & first argument precedes \\
\verb|    const difference_counter& y)|    &                           & the second.             \\ \hline
\verb|difference_counter& operator++ ()|   &                           & Preincrement            \\ \hline
\verb|difference_counter operator++ (int)| &                           & Postincrement           \\ \hline
\verb|difference_counter& operator-- ()|   &                           & Predecrement            \\ \hline
\verb|difference_counter operator-- (int)| &                           & Postdecrement           \\ \hline
\verb|difference_counter operator<<|       &                           & Shift left              \\
\verb|   (int x)|                          &                           &                         \\ \hline
\verb|difference_counter& operator<<=|     &                           & Shift left              \\
\verb|   (int x)|                          &                           &                         \\ \hline
\verb|difference_counter operator>>|       &                           & Shift right             \\
\verb|   (int x)|                          &                           &                         \\ \hline
\verb|difference_counter& operator>>=|     &                           & Shift right             \\
\verb|   (int x)|                          &                           &                         \\ \hline
\verb|difference_counter operator+|        &                           & addition                \\
\verb|   (const difference_counter& y)|    &                           &                         \\ \hline
\verb|Iterator operator+|                  & Random Access Iterator    & Iterator addition       \\
\verb|   (const Iterator& y)|              &                           &                         \\ \hline
\verb|Iterator operator+|                  & Random Access Iterator    & Iterator addition       \\
\verb|   (const Iterator& i,|              &                           &                         \\
\verb|    const difference_counter& n)|    &                           &                         \\ \hline
\verb|difference_counter& operator+=|      &                           & addition                \\
\verb|   (const difference_counter& y)|    &                           &                         \\ \hline
\verb|Iterator& operator+=|                & Random Access Iterator    & Iterator addition       \\
\verb|   (const Iterator& i,|              &                           &                         \\
\verb|    const difference_counter& y)|    &                           &                         \\ \hline
\verb|difference_counter operator-|        &                           & subtraction             \\
\verb|   (const difference_counter& y)|    &                           &                         \\ \hline
\verb|Iterator operator-|                  & Random Access Iterator    & Iterator subtraction    \\
\verb|   (const Iterator& i,|              &                           &                         \\
\verb|    const difference_iterator& n)|   &                           &                         \\ \hline
\verb|difference_counter& operator-=|      &                           & subtraction             \\
\verb|   (const difference_counter& y)|    &                           &                         \\ \hline
\verb|Iterator& operator-=|                & Random Access Iterator    & Iterator subtraction    \\
\verb|   (const Iterator& i,|              &                           &                         \\
\verb|    const Difference& y)|            &                           &                         \\ \hline
\verb|difference_counter operator*|        &                           & multiplication          \\
\verb|   (const difference_counter& y)|    &                           &                         \\ \hline
\verb|difference_counter operator*=|       &                           & multiplication          \\
\verb|   (const difference_counter& y)|    &                           &                         \\ \hline
\verb|difference_counter operator/|        &                           & division                \\
\verb|   (const difference_counter& y)|    &                           &                         \\ \hline
\verb|difference_counter operator/=|       &                           & division                \\
\verb|   (const difference_counter& y)|    &                           &                         \\ \hline
\end{tabular}
}
\subsection{New Members}
These members are not defined in the concept requirements, but are specific to 
\verb|difference_counter|.\\

\small{
\begin{tabular}{|l|l|}                                                                      \hline
Member                          & Description                                            \\ \hline
\verb|difference_counter|       & This constructor takes the object n of the base        \\
\verb|   (const Difference& x)| & class and create an \verb|difference_counter| with it. \\ \hline
\verb|Difference base()|        & Returns the current value of the                       \\
                                & \verb|difference_counter|'s base difference.           \\ \hline
\end{tabular}
\subsection{Notes}
None

\section{value\_counter\small{$<$Value,Name,Counter$>$}}

\subsection{Description}
\verb|value_counter| is an adaptor around an Element to which an iterator points.
It counts how often each method on an element is called.  Like all counting
adaptors, the counts are stored in a \verb|counter_vector| and
recorded by the \verb|recorder| after each iteration.  


\subsection{Example of use}

@D \verb|value_counter| example of use
@{
  typedef value_counter<int> counted_int;

  recorder<> r;

  counted_int val1(1234);
  counted_int val2(val1);

  bool b = (val1 == val2);

  r.record();
  cout << r;
@}
In this example, one external constructor, one copy constructor and one 
Equality is counted.


\subsection{Definition}
Defined in \verb|counters.h|

\subsection{Template parameters}
\small{
\begin{tabular}{|l|l|l|}                                                                               \hline
Parameter       & Description                                  & Default                            \\ \hline
Value           & The base value class to be adapted.          &                                    \\ \hline
Name            & The Name, which is used for the recorder.    & null                               \\
                & If it is null, "\verb|difference_counter|" is used. &                             \\ \hline
Counter         & The type which is used for the counting.     & unsigned long                      \\ \hline
\end{tabular}
}
\subsection{Model of}
Assignable, Default Constructible, Equality Comparable, LessThan Comparable

\subsection{Type requirements}
The base value type must be at least a model of Assignable and Default Constructible.

\subsection{Public base classes}
None.

\subsection{Members}
\small{
\begin{tabular}{|l|l|l|}                                                                            \hline
Member                                & Where Defined             & Description             \\ \hline
\verb|value_counter()|                & Default Constructible     & The default             \\
                                      &                           & constructor             \\ \hline
\verb|value_counter|                  & Assignable                & The copy constructor    \\
\verb|   (const value_counter& x)|    &                           &                         \\ \hline
\verb|value_counter& operator=|       & Assignable                & The assignment          \\ 
\verb|   (const value_counter& y)|    &                           & operator                \\ \hline
\verb|value_counter|                  & \verb|value_counter|      & see below               \\
\verb|   (const Value& x)|            &                           &                         \\ \hline
\verb|Value base()|                   & \verb|value_counter|      & see below               \\ \hline
\verb|bool operator==|                & Equality Comparable       & Compares two            \\        
\verb|   (const value_counter& x|     &                           & iterators for           \\ 
\verb|    const value_counter& y)|    &                           & equality.               \\ \hline
\verb|bool operator<|                 & LessThan Comparable       & Determines whether      \\
\verb|   (const value_counter& x,|    &                           & the first argument      \\
\verb|    const value_counter& y)|    &                           & precedes the second.    \\ \hline
\verb|value_counter& operator++ ()|   &                           & Preincrement            \\ \hline
\verb|value_counter operator++ (int)| &                           & Postincrement           \\ \hline
\verb|value_counter& operator-- ()|   &                           & Predecrement            \\ \hline
\verb|value_counter operator-- (int)| &                           & Postdecrement           \\ \hline
\verb|value_counter operator<<|       &                           & Shift left              \\
\verb|   (int x)|                     &                           &                         \\ \hline
\verb|value_counter& operator<<=|     &                           & Shift left              \\
\verb|   (int x)|                     &                           &                         \\ \hline
\verb|value_counter operator>>|       &                           & Shift right             \\
\verb|   (int x)|                     &                           &                         \\ \hline
\verb|value_counter& operator>>=|     &                           & Shift right             \\
\verb|   (int x)|                     &                           &                         \\ \hline
\verb|value_counter operator+|        &                           & addition                \\
\verb|   (const value_counter& y)|    &                           &                         \\ \hline
\verb|value_counter& operator+=|      &                           & addition                \\
\verb|   (const value_counter& y)|    &                           &                         \\ \hline
\verb|value_counter operator-|        &                           & subtraction             \\
\verb|   (const value_counter& y)|    &                           &                         \\ \hline
\verb|value_counter& operator-=|      &                           & subtraction             \\
\verb|   (const value_counter& y)|    &                           &                         \\ \hline
\verb|value_counter operator*|        &                           & multiplication          \\
\verb|   (const value_counter& y)|    &                           &                         \\ \hline
\verb|value_counter operator*=|       &                           & multiplication          \\
\verb|   (const value_counter& y)|    &                           &                         \\ \hline
\verb|value_counter operator/|        &                           & division                \\
\verb|   (const value_counter& y)|    &                           &                         \\ \hline
\verb|value_counter operator/=|       &                           & division                \\
\verb|   (const value_counter& y)|    &                           &                         \\ \hline
\end{tabular}
}
\subsection{New Members}
These members are not defined in the concept requirements, but are specific to 
\verb|value_counter|.\\

\small{
\begin{tabular}{|l|l|}                                                                    \hline
Member                      & Description                                              \\ \hline
\verb|value_counter|        & This constructor takes the object x of the base          \\
\verb|    (const Value& x)| & class and create an \verb|value_counter| with it.        \\ \hline
\verb|Value base()|         & Returns the current value of the \verb|value_counter|'s  \\
                            & base value.                                              \\ \hline
\end{tabular}
\subsection{Notes}
None.

\section{generator\_counter\small{$<$AdaptableGenerator,Name,Counter$>$}}
\subsection{Description}
\verb|generator_counter| is an adaptor around an adaptable generator.
It counts how often each method on the generator is called.

\subsection{Example of use}

@D \verb|generator_counter| example of use
@{
  typedef generator_counter<myGenerator> adap_my_gen;

  recorder<> r;

  adap_my_gen::result_type res;
  adap_my_gen              gen;

  res = gen();

  r.record();
  cout << r;
@}

\subsection{Definition}
Defined in \verb|counters.h|

\subsection{Template parameters}
\small{
\begin{tabular}{|l|l|l|}                                                                               \hline
Parameter          & Description                                  & Default                            \\ \hline
AdaptableGenerator & The base generator class to be adapted.      &                                    \\ \hline
Name               & The Name, which is used for the recorder.    & null                               \\
                   & If it is null, "\verb|difference_counter|" is used. &                             \\ \hline
Counter            & The type which is used for the counting.     & unsigned long                      \\ \hline
\end{tabular}
}
\subsection{Model of}
Adaptable Generator

\subsection{Type requirements}
The generator must be an adaptable generator.

\subsection{Public base classes}
None.

\subsection{Members}
\small{
\begin{tabular}{|l|l|l|}                                                                     \hline
Member                                    & Where Defined             & Description       \\ \hline
\verb|generator_counter()|                & Default Constructible     & The default       \\
                                          &                           & constructor       \\ \hline
\verb|generator_counter|                  & Assignable                & The copy          \\
\verb|   (const generator_counter& x)|    &                           & constructor       \\ \hline
\verb|generator_counter& operator=|       & Assignable                & The assignment    \\ 
\verb|   (const generator_counter& y)|    &                           & operator          \\ \hline
\verb|generator_counter|                  & \verb|generator_counter|  & see below         \\
\verb|   (const Generator& x)|            &                           &                   \\ \hline
\verb|result_type operator() ()|          & Adaptable Generator       & The generator     \\        
                                          &                           & call itself       \\ \hline
\end{tabular}
}
\subsection{New Members}
These members are not defined in the concept requirements, but are specific to 
\verb|generator_counter|.\\

\small{
\begin{tabular}{|l|l|}                                                                    \hline
Member                          & Description                                           \\ \hline
\verb|generator_counter|        & This constructor takes the object x of the base       \\
\verb|    (const Generator& x)| & class and create an \verb|generator_counter| with it. \\ \hline
\end{tabular}
\subsection{Notes}
None.

\section{unary\_function\_counter\small{$<$AdaptableUnaryFunction,Name,Counter$>$}}
\subsection{Description}
\verb|unary_function_counter| is an adaptor around an adaptable unary function.
It counts how often each method on the unary function is called.

\subsection{Example of use}

@D \verb|unary_function_counter| example of use
@{
  typedef identity<int> myUnary_Function;
  typedef unary_function_counter<myUnary_Function> adap_my_uf;

  recorder<> r;

  adap_my_uf::result_type    res;
  adap_my_uf::argument_type  arg;
  myUnary_Function           f;
  adap_my_uf                 uf(f);

  res = uf(arg);

  r.record();
  cout << r;
@}

\subsection{Definition}
Defined in \verb|counters.h|

\subsection{Template parameters}
\small{
\begin{tabular}{|l|l|l|}                                                                  \hline
Parameter              & Description                                  & Default        \\ \hline
AdaptableUnaryFunction & The base unary function class to be adapted. &                \\ \hline
Name                   & The Name, which is used for the              & null           \\
                       & recorder. If it is null,                     &                \\
                       & "\verb|unary_function_counter|" is used.     &                \\ \hline
Counter                & The type which is used for the counting.     & unsigned long  \\ \hline
\end{tabular}
}
\subsection{Model of}
Adaptable Unary Function

\subsection{Type requirements}
The unary function must be adaptable.

\subsection{Public base classes}
None.

\subsection{Members}
\small{
\begin{tabular}{|l|l|l|}                                                                             \hline
Member                                     & Where Defined                  & Description         \\ \hline
\verb|unary_function_counter()|            & Default Constructible          & The default         \\
                                           &                                & constructor         \\ \hline
\verb|unary_function_counter|              & Assignable                     & The copy            \\
\verb|  (const unary_function_counter& x)| &                                & constructor         \\ \hline
\verb|unary_function_counter& operator=|   & Assignable                     & The assignment      \\ 
\verb|  (const unary_function_counter& y)| &                                & operator            \\ \hline
\verb|unary_function_counter|              & \verb|unary_function_counter|  & see below           \\
\verb|  (const AdaptableUnaryFunction& x)| &                                &                     \\ \hline
\verb|result_type operator()|              & Adaptable Unary Function       & The unary function  \\
\verb|  (const argument_type& a)|          &                                & call itself         \\ \hline
\end{tabular}
}
\subsection{New Members}
These members are not defined in the concept requirements, but are specific to 
\verb|unary_function_counter|.\\

\small{
\begin{tabular}{|l|l|}                                                                    \hline
Member                                       & Description                             \\ \hline
\verb|unary_function_counter|                & This constructor takes the object x of  \\
\verb|    (const AdaptableUnaryFunction& x)| & the base class and create an            \\
                                             & \verb|unary_function_counter| with it.  \\ \hline
\end{tabular}
\subsection{Notes}
None.

\section{binary\_function\_counter\small{$<$AdaptableBinaryFunction,Name,Counter$>$}}
\subsection{Description}
\verb|binary_function_counter| is an adaptor around an adaptable binary function.
It counts how often each method on the binary function is called.

\subsection{Example of use}

@D \verb|binary_function_counter| example of use
@{
  typedef equal_to<int> myBinary_Function;
  typedef binary_function_counter<myBinary_Function> adap_my_bf;

  recorder<> r;

  adap_my_bf::result_type           res;
  adap_my_bf::first_argument_type   arg1;
  adap_my_bf::second_argument_type  arg2;
  myBinary_Function                 f;
  adap_my_bf                        bf(f);

  res = bf(arg1, arg2);

  r.record();
  cout << r;
@}

\subsection{Definition}
Defined in \verb|counters.h|

\subsection{Template parameters}
\small{
\begin{tabular}{|l|l|l|}                                                                  \hline
Parameter               & Description                                 & Default        \\ \hline
AdaptableBinaryFunction & The base binary function class to be        &                \\
                        & adapted.                                    &                \\ \hline
Name                    & The Name, which is used for the             & null           \\
                        & recorder. If it is null,                    &                \\
                        & "\verb|binary_function_counter|" is used.   &                \\ \hline
Counter                 & The type which is used for the counting.    & unsigned long  \\ \hline
\end{tabular}
}
\subsection{Model of}
Adaptable Binary Function

\subsection{Type requirements}
The binary function must be adaptable.

\subsection{Public base classes}
None.

\subsection{Members}
\small{
\begin{tabular}{|l|l|l|}                                                                             \hline
Member                                      & Where Defined                  & Description         \\ \hline
\verb|binary_function_counter()|            & Default Constructible          & The default         \\
                                            &                                & constructor         \\ \hline
\verb|binary_function_counter|              & Assignable                     & The copy            \\
\verb|  (const binary_function_counter& x)| &                                & constructor         \\ \hline
\verb|binary_function_counter& operator=|   & Assignable                     & The assignment      \\ 
\verb|  (const binary_function_counter& y)| &                                & operator            \\ \hline
\verb|binary_function_counter|              & \verb|binary_function_counter| & see below           \\
\verb|  (const AdaptableBinaryFunction& x)| &                                &                     \\ \hline
\verb|result_type operator()|               & Adaptable Binary Function      & The binary function  \\
\verb|  (const first_argument_type& x,|     &                                & call itself         \\
\verb|   const second_argument_type& y)|    &                                &                     \\ \hline
\end{tabular}
}
\subsection{New Members}
These members are not defined in the concept requirements, but are specific to 
\verb|binary_function_counter|.//

\small{
\begin{tabular}{|l|l|}                                                                      \hline
Member                                        & Description                              \\ \hline
\verb|binary_function_counter|                & This constructor takes the object x of   \\
\verb|    (const AdaptableBinaryFunction& x)| & the base  class and create an            \\
                                              &  \verb|binary_function_counter| with it  \\  \hline
\end{tabular}
\subsection{Notes}
None.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Design Issues}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Implicit Constructors}

Many operations implicitly invoke a constructor, perhaps more than
once.  For example, the post-increment operator normally returns a new
object containing the result of the increment.  Should these calls be
counted explicitly or should they be considered to be an understood
part of the operation that invokes the constructor?

The library does not count these calls separately.  The motivation is
that in order to properly analyze the operation counting results, the
user must understand the relative costs of each operation.  Since
those costs may vary from type to type, it should not be up to the
library to capture that information.  Furthermore, counting the
implicit constructor invocations that occur at the adaptor level could
result in inaccurate result reporting.  Consider the following
example.

@d Implicit Constructors example 1 
@{self& operator++ (int) {
  return *this;
}
@}

This is not an unrealistic example.  In fact, this code is essentially
equivalent to the post-increment operator of the STL
\verb|back_insert_iterator|.  In this case, there is no implicit call
of the constructor.  The post-increment operator is extremely
efficient.  However, the most natural implementation of a counting
post-increment operator would count two constructor calls, as shown
below.

@d Implicit Constructors example 2 
@{self operator++ (int) {
  ++counters[POST_INCREMENT];
  self return_value (*this);  // first copy ctor call
  base_iterator++;
  return return_value; // second copy ctor call
}
@}

For this reason, the counting adaptors implement a special private
constructor that is not counted.

\section{Default Counter Type}

In the general case, operation counts may become quite large, larger
even than the built-in C\textsuperscript{++} integer types are able to
manage.  To accommodate this situation, all of the counting adaptors
are parameterized on the type of the counter.  This allows the user to
choose an alternate integral type, for instance one that models
integers of arbitrary length.

Although this feature is useful it is also somewhat inconvenient to
use, since to override the default, each instantiation of a counting
class must specify the counter type parameter.  To simplify the
library's use, the default type is actually given by a C preprocessor
constant, \verb|DEFAULT_COUNTER_TYPE|.  If this is predefined at
compile time, its value will be used as the default counter type.
Otherwise the library default of \verb|unsigned long| will be
substituted.

@d default counter type 
@{#ifndef DEFAULT_COUNTER_TYPE
#  define DEFAULT_COUNTER_TYPE unsigned long
#endif
@}

\section{Enumeration Constants}

One option considered for the indices used to refer to elements of the
counter vector was to index by member function pointers.  This would
result in a syntax such as is shown below.

@d Enumeration Constants example 1 
@{// increment the count of assignments
++counters[&operator=];
@}

This approach has the desirable property that the counters are tied
very directly and intuitively to the function that they are counting.
There are a number of problems with this approach, however, that
eventually caused it to be abandoned.

The most critical problem was that not all of the counted operations
are implemented as member functions.  Thus, indexing by member
function pointer is not meaningful in some contexts.  For example, a
constructor is not a regular member function.  Similarly, comparison
operations such as \verb|operator==| are generally implemented as
global functions.

For this reason the choice was made to use enumerated numeric
constants with names chosen to correspond to the operations.  This
presented an additional question as to where to define the enumeration
type.  It could have global scope or it could be nested in one of the
library's classes.

The advantage to global scope is ease of reference.  If the
enumeration is nested in another class, the constants must be prefixed
by the class name and scope resolution operator.

@d Enumeration Constants example 2 
@{// global enumeration type
enum { CONSTANT1, CONSTANT2, /* ... */ };

// ...
++counters[CONSTANT1];
@}

@d Enumeration Constants example 3 
@{// nested enumeration type
class Foo {
 public:
  enum { CONSTANT1, CONSTANT2, /* ... */ };
};

// ...
++counters[Foo::CONSTANT1];
@}

Based on this argument it would appear that a global type is better,
however, it was feared that the constants would infringe on the user's
namespace.  Thus, they would need to be prefixed somehow, perhaps
resulting in names such as \verb|COUNTERS_CONSTANT1|.  At this point
then both approaches are quite similar.

The final decision was to utilize \verb|nuweb|'s ability to define
repeated ``parts'' in order to include the enumeration as a nested
type in each counting adaptor.  Then the adaptors themselves can refer
to the enumeration constants without any prefix.  Library users will
not normally need to use the constants directly, but if that is
necessary, they can be accessed through the \verb|recorder| class
which declares its enumeration to be public.

\section{Counter Vectors}
The \verb|counter_vector| class derived from a standard vector, and is
used to hold counts for each operation within each counter adaptor.
Each adaptor instantiates a
% forced line-break due to overfull hbox
\\\verb|counter_vector|, and registers this
vector with the \verb|recorder|.

\label{sec:des:counter_reg}

Registration of an adaptor's \verb|counter_vector| is done
automatically by the
% forced line-break due to overfull hbox
\\\verb|counter_vector|'s constructor.  It calls
\verb|recorder<>::insert()|, which adds the vector to the
\verb|recorder|'s counter registry.

\section{Printable Names}

\label{sec:des:print_name}
To provide for flexibility in the reporting of results, it is
desirable to be able to associate a printable name with each counting
adaptor type.  In this way, the counts for operations applied to
\verb|int|'s may be reported separately from those on \verb|float|'s
and \verb|vector<int>|'s for example.  This can be an important
distinction since the relative cost of operations on each data type
may vary.

At the same time, however, it should not be necessary for the library
user to explicitly name each adaptor class that is used.  A suitable
default should be chosen by the library if a name is not explicitly
given.  This presents a number of problems.

The approach chosen is to parameterize the adaptor types with an
optional \verb|Name| argument.  One alternative considered for the
default was the type name provided by the C\textsuperscript{++}
runtime type identification mechanism.  The standard does not,
however, provide any specific requirements on that name and in
practice it is not readily interpreted by a human.

As a result, the default value does not make reference to the
parameterized type of the adaptor.  For example, all
\verb|iterator_counter| variants will be reported as
``iterator\_counter'' regardless of the underlying iterator type.
However, if the user desires finer grained reporting a more specific
name may be given as a template parameter.\footnote{The {\tt Name}
template parameter is only available if the 
{\tt COUNTERS\_USE\_PRINTABLE\_NAMES} preprocessor variable is
defined. It is not by default because it does not work with 
{\tt g++ 2.8.1}. } 

This results in class declarations such as the following.

@d Printable Names example 1 
@{template <const char* const Name = "iterator_counter">
class iterator_counter {
  // ...
};
@}

Unfortunately, this is not actually legal C\textsuperscript{++} code.
A template argument of pointer type must be an object with external
linkage.  String literals have internal linkage.  As a result, it is
necessary to use a special default (non-pointer\footnote{
Strangely enough, arrays are considered to be non-pointers in this
situation.  So a char[] works when a char* would not.}) object that
represents the default value.  The template argument can later be
tested for equality to the default object, and appropriate actions may
be taken.  This provides the revised class declaration shown below.

@d Printable Names example 2 
@{template <const char* const Name = counter_vector<>::null>
class iterator_counter {
  // ...
  // example use of Name:
  //    (*Name == '\0') ? "iterator_counter" : Name
};
@}

All counting adaptors should use this or another similar mechanism to
obtain the name used for reports and counter registration.

\section{Printable Names Bug}

\label{sec:des:print_name_bug}
There is yet another problem related to the issue of printable names
for the counting class adaptors.  Many compilers are unable to handle
the default argument for the \verb|Name| parameter.  For example,
\verb|g++ 2.8.1| encounters an ``internal compiler error'' when the
counting adaptors are used.

For this reason the printable name feature is guarded by conditional
compilation directives.  For the time being, since it appears to be a
problem more often than not, the default is not to use this feature.
If the library user wishes to use printable names and has a compiler
that is capable enough for the feature, the defining preprocessor
constant \verb|COUNTERS_USE_PRINTABLE_NAMES| will enable the feature.

\section{Source Code Legibility}

\verb|nuweb| tends to introduce a lot of blank lines in the resulting
source code files even if we disable the \verb|#line| printing option.
This makes them somewhat hard to browse.  A one-line perl script can
be run from the Makefile (the \verb|source| target) to clean up the
source files, should one wish to read them directly.  This script
simply removes the \verb|#line| directives and collapses multiple
blank lines to a single one.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Source Code}

\section{General}

The following C preprocessor directives are available for customizing
the behavior of the code for specific compilers or environments:\\

\begin{tabular}{|l|l|l|}
\hline
Variable                      & Default           & Description\\
\hline
\verb|COUNTERS_USE_PRINTABLE_NAMES| & \verb|undefined|     & 
                                          Define to enable the Name template\\ 
                                    &                      &
                                          parameter on the counters. It must\\
                                    &                      &
                                          be undefined for g++ 2.8.1\\
                                    &                      &
                                          due to a compiler bug.\\
\hline
\verb|DEFAULT_COUNTER_TYPE|         & \verb|unsigned long| &
                                          Type to use for operation counts.\\
\hline
\end{tabular}

\label{sec:src:print_name_bug}
\section{Printable Names Bug}

As discussed in the Design Issues chapter, there is a problem with
using a default argument for the counting adaptors' printable name
(see section \ref{sec:des:print_name}, page
\pageref{sec:des:print_name} and section \ref{sec:des:print_name_bug},
page \pageref{sec:des:print_name_bug}).  Thus that part of the code is
conditionalized.  There are four forms in which the Name parameter may
be referenced.  The code shown below is used later by each class when
implementing aspects of the printable name feature.

@d printable names bug definitions 
@{#ifdef COUNTERS_USE_PRINTABLE_NAMES
#  define COUNTERS_NAME_DECL_DEFAULT \
          const char* const Name = counter_vector<>::null,
#  define COUNTERS_NAME_DECL const char* const Name,
#  define COUNTERS_NAME_PARM Name,
#  define COUNTERS_NAME_TEST (*Name == '\0')
#else
#  define COUNTERS_NAME_DECL_DEFAULT
#  define COUNTERS_NAME_DECL
#  define COUNTERS_NAME_PARM
#  define COUNTERS_NAME_TEST true
#endif
@}

\label{sec:src:enum}
To simplify totalling the operation counts computed by the different
adaptors an enumeration type is provided to code the types of
operations.  The counts themselves are kept in a vector indexed by the
enumerations.

@d counter index enumeration 
@{enum operator_type {
  DEFAULT_CTOR, COPY_CTOR, 
  OTHER_CTOR, BASE, DTOR, GENERATION,
  ASSIGNMENT, CONVERSION, LESS_THAN, EQUALITY,
  POST_INCREMENT, PRE_INCREMENT, 
  POST_DECREMENT, PRE_DECREMENT, 
  PLUS, MINUS, TIMES, DIVIDE, MODULO,
  LEFT_SHIFT, RIGHT_SHIFT,
  PLUS_ASSIGN, MINUS_ASSIGN, 
  TIMES_ASSIGN, DIVIDE_ASSIGN, MODULO_ASSIGN,
  LEFT_SHIFT_ASSIGN, RIGHT_SHIFT_ASSIGN,
  DEREFERENCE, SUBSCRIPT, FUNCTION_CALL,
  OSTREAM, ISTREAM,
  NCOUNTERS,
};
@}

This enumeration is made available to all of our classes by using
nuweb's macro capability to replicate this definition to all of our
classes.   They are accessible to other code as
\verb|counter_vector<>::operator_type|.

For reporting purposes, a \verb|counter_tags| array is defined in the
recorder to map these enums to textual descriptions.

@d \verb|counter_tags| definition 
@{  "x()", "x(y)",
  "x(?)", "base", "~x", "gen",
  "op=", "cast()", "op<", "op==",
  "op++", "++op", 
  "op--", "--op",
  "op+", "op-", "op*", "op/", "op\%",
  "op<<", "op>>",
  "op+=", "op-=", "op*=", "op/=", "op\%=",
  "op<<=", "op>>=",
  "*op", "op[]", "op()",
  "cout<<", "cin>>",
@}

Each counter adaptor needs to keep track of a count for each of these
count types.  Rather than using a vector of counters (of
\verb|DEFAULT_COUNTER_TYPE|), indexed by
% forced line-break due to overfull hbox
\\\verb|operator_type|s, a
\verb|counter_vector| class is defined.  This class is just a vector,
but it adds a constructor which automatically registers the counter
with the recorder class (discussed in the Design Issues section, page
\pageref{sec:des:counter_reg}).

@d \verb|counter_vector| 
@{template <class Counter = DEFAULT_COUNTER_TYPE> class recorder;

template <class Counter = DEFAULT_COUNTER_TYPE>
class counter_vector : public vector<Counter> {
 public:
  counter_vector () : vector<Counter>(recorder<>::NCOUNTERS) {}
  counter_vector (const char* const name) : vector<Counter>() {
    recorder<Counter>::insert(name, this);
  }
  counter_vector (const char* const name, size_type n) 
    : vector<Counter>(n) {
    recorder<Counter>::insert(name, this);
  }
  static char null[];
};
template <class Counter>
char counter_vector<Counter>::null[] = "";
@}

\section{Recorder}

The \verb|recorder| class is used for tracking and reporting the
results of operation counting.  By default a \verb|recorder| manages
all counting adaptors.  Alternatively it is possible to create a
recorder for a specific subset of the adaptors or operations.

The \verb|recorder| class keeps a static registry of the
\verb|counter_vector|s for all counting adaptor classes.  This is used
primarily when creating a default recorder, to allow it to record all
known counters.  Each \verb|counter_vector| is automatically added to
the registry when it is constructed by calling \verb|recorder|'s
\verb|insert()| method.  As a static member, the registry is therefore
shared between all recorder instances (if more than one registry is
declared).

@d \verb|recorder| registry of all counters declaration 
@{static map_type* registry;
@}

@d \verb|recorder| registry of all counters definition 
@{template <class Counter>
recorder<Counter>::map_type* recorder<Counter>::registry;
@}

@d \verb|recorder| \verb|insert()| method 
@{static bool insert (const string& x, counter_vector<Counter>* y) {
  if (registry == NULL)
    registry = new map_type();
  registry->insert(map_type::value_type(x, y));
  return true;
}
@}

The \verb|recorder| uses two member variables to keep track of the
counting information.  First is a map that contains pointers to all of
the \verb|Counter| vectors managed by the \verb|recorder|.  This map
is analagous to the registry but contains only those counters that are
being managed by a particular \verb|recorder| instance.

@d \verb|recorder| counter map 
@{typedef multimap<string, counter_vector<Counter>*> map_type;
map_type counters;
@}

The second member variable contains snapshots of the counter values at
various instances in time.  Typically the library user would perform
some set of tests, then record the counter values and reset them to
zero.  The \verb|recorder|'s reporting functions provide a variety of
ways to analyze the counter snapshots.

The snapshots are a three-dimensional data structure (see Figure
\ref{fig:snapshot}).  The first index
is over the snapshots themselves and thus represents time or
iterations.  Then each snapshot has two dimensions.  The first is the
counter adaptor type which is represented by a string.  The second
index is the operation which is represented by a constant of the
\verb|operator_type| enumeration.

\begin{figure}
  \begin{center}
    \includegraphics{recorder.eps}
  \end{center}
  \caption{Snapshot Data Structure}
  \label{fig:snapshot}
\end{figure}


@d \verb|recorder| snapshot data 
@{typedef multimap<string, counter_vector<Counter> > snapshot_type;
vector<snapshot_type> snapshots;

typedef map<string, counter_vector<Counter> > datum_type;
vector<datum_type> data;
@}

Again, by default a \verb|recorder| is initialized to manage all known
counters.

@d \verb|recorder| constructor 
@{recorder () : counters(*registry), data() {
  report_init();
}
@}

Typical use of the counting adaptor classes will involve running a
series of test sequences creating multiple data points for analysis.
After each experiment the \verb|record()| method should be called.
This saves the current values of the counters in a snapshot and resets
their values to 0.  The library user may also temporarily pause
counting via the \verb|pause()| and \verb|resume()| members.  This is
useful when performing setup steps to prepare for a test, such as
creating the test data.  It is not generally desirable to include
these steps in the algorithm analysis.

@d \verb|recorder| \verb|pause()| method 
@{void pause () { 
  snapshots.push_back(snapshot_type());
  snapshot_type& snapshot = snapshots.back();
  for (map_type::iterator i = counters.begin(); 
       i != counters.end(); 
       ++i)
    snapshot.insert(snapshot_type::value_type(i->first, 
                                              *i->second));
}
@}

@d \verb|recorder| \verb|resume()| method 
@{void resume () { 
  snapshot_type& snapshot = snapshots.back();
  map_type::iterator mi;
  snapshot_type::iterator si;
  for (mi = counters.begin(), si = snapshot.begin(); 
       (mi != counters.end()) && (si != snapshot.end()); 
       ++mi, ++si)
    *mi->second = si->second;
  snapshots.pop_back(); 
}
@}

@d \verb|recorder| \verb|record()| method 
@{void record () {
  data.push_back(datum_type());
  datum_type& datum = data.back();
  for (map_type::iterator i = counters.begin(); 
       i != counters.end(); 
       ++i) {
    counter_vector<Counter>& elt = datum[i->first];
    if (elt.size() < i->second->size())
      elt.reserve(i->second->size());
    for (size_t j = 0; j < i->second->size(); ++j)
      elt[j] += (*i->second)[j];
  }
  reset();
}
@}

@d \verb|recorder| \verb|reset()| method 
@{void reset () {
  for (map_type::iterator i = counters.begin(); 
       i != counters.end(); 
       ++i)
    for (size_t j = 0; j < i->second->size(); ++j)
      (*i->second)[j] = 0;
}
@}

Finally there are a variety of methods for reporting and analyzing the
results.  These use an array that maps indices in the counter vectors
to printable strings.

@d \verb|recorder| print string declaration 
@{static const char* const counter_tags[NCOUNTERS];
@}

@d \verb|recorder| print string definition 
@{template <class Counter>
const char* const recorder<Counter>::counter_tags[NCOUNTERS] = {
@<\verb|counter_tags| definition@>
};
@}

The reporting functions shown below can output a delimited (with tabs
by default) table of results.  The \verb|report_headings()| method
simply prints list of column titles for the table.  The
\verb|report_table| function lists out one line of counts for each
printable name.  Finally the \verb|report_totals()| method prints the
total over all printable names.

These functions take a sequence operation which operates on the
snapshots in the time dimension.  Thus, for a sequence of snapshots it
is possible to obtain the median, minimum, maximum or some other
statistic.

@d \verb|recorder| \verb|report_headings()| method 
@{ostream& report_headings (ostream& out,
                          const char* delim = "\t") const {
  out << "Type";
  for (size_t i = 0; 
       i < sizeof(counter_tags)/sizeof(counter_tags[0]);
       ++i)
    if (op_filter[i])
      out << delim << counter_tags[i];
  return out << endl;
}
@}

@d \verb|recorder| \verb|report_table()| method 
@{template <class SequenceOperation>
ostream& report_table (ostream& out,
                       const SequenceOperation& op,
                       const char* delim = "\t") const {
  counter_vector<Counter> tmp;
  for (datum_type::const_iterator i = data.front().begin();
       i != data.front().end();
       ++i) {
    out << i->first << delim;

    for (size_t j = 0; j < i->second.size(); ++j) {
      if (!op_filter[j]) continue;
      tmp.erase(tmp.begin(), tmp.end());
      for (size_t k = 0; k < data.size(); ++k)
        tmp.push_back(data[k].find(i->first)->second[j]);

      Counter x = *op(tmp.begin(), tmp.end());
      out << x << delim;
    }

    out << endl;
  }
  return out;
}
@}

@d \verb|recorder| \verb|report_totals()| method 
@{template <class SequenceOperation>
ostream& report_totals (ostream& out,
                        const SequenceOperation& op,
                        const char* delim = "\t") const {
  out << "Total" << delim;
  counter_vector<Counter> tmp;
  for (size_t op_idx = 0; op_idx < NCOUNTERS; ++op_idx) {
    if (!op_filter[op_idx]) continue;
    tmp.erase(tmp.begin(), tmp.end());

    for (size_t j = 0; j < data.size(); ++j) {
      tmp.push_back(0);

      datum_type::const_iterator k;   
      for (k = data[j].begin(); k != data[j].end(); ++k)
        if (op_idx == GENERATION)
	  tmp[j] = max(tmp[j], k->second[op_idx]);
	else
	  tmp[j] += k->second[op_idx];
    }

    // At this point, tmp is a vector of counts of this operation.
    // apply the functor to get a single count from this set (max,
    // min, etc)
    Counter x = *op(tmp.begin(), tmp.end());

    out << x << delim;
  }
  return out << endl;
}
@}

@d \verb|recorder| \verb|report()| method 
@{template <class SequenceOperation>
ostream& report (ostream& out, 
                  const SequenceOperation& op) const {
  counter_vector<Counter> tmp;

  // this seems to be necessary for egcs, although I am not
  // sure why.  For some reason the linker can not find the
  // regular static copy of counter_tags.

  const char* const counter_tags[NCOUNTERS] = {
    @<\verb|counter_tags| definition@>
  };

  for (size_t op_idx = 0; op_idx < NCOUNTERS; ++op_idx) {
    if (! op_filter[op_idx]) continue;

    tmp.erase(tmp.begin(), tmp.end());

    for (size_t j = 0; j < data.size(); ++j) {
      tmp.push_back(0);

      datum_type::const_iterator k;   
      for (k = data[j].begin(); k != data[j].end(); ++k)
        if (op_idx == GENERATION)
	  tmp[j] = max(tmp[j], k->second[op_idx]);
	else
	  tmp[j] += k->second[op_idx];
    }

    // At this point, tmp is a vector of counts of this operation.
    // apply the functor to get a single count from this set (max,
    // min, etc)
    Counter x = *op(tmp.begin(), tmp.end());

    if (! show_zero && x == 0) continue;

    out << setw(6) << setiosflags(ios::right);
    out << counter_tags[op_idx];
    out << resetiosflags (ios::left); 
    out << " = " << x << endl;
  }
  return out;
}
@}

The \verb|median_element()| function shown below works similarly to
the STL functions \verb|min_element()| and \verb|max_element()|.  It
operates on a sequence and returns the median value.  The elements of
the sequence must implement the \verb|Less Than Comparable| concept.

This function is useful for analyzing a sequence of trials of an
algorithm.  Other statistics such as minimum, maximum or mean are very
sensitive to outlier cases from near best case or near worst case
data.  The median is less susceptible to this problem.  For this
reason, the \verb|recorder| class uses the median of its results by
default.  For a good discussion on the utility of the median in
performance analysis see \cite{musser:timing}.

@d \verb|median_element| functor 
@{template <class ForwardIterator>
ForwardIterator median_element(ForwardIterator first, 
			       ForwardIterator last) {
  typedef typename iterator_traits<ForwardIterator>::value_type T;

  // because nth_element is mutative, we must copy the range to a
  // temporary container.
  vector<T> tmp(last - first);
  copy (first,last,tmp.begin());
  
  vector<T>::iterator midpoint = (tmp.begin() + 
				  (tmp.end() - tmp.begin()) / 2);
  nth_element(tmp.begin(), midpoint, tmp.end());

  // OK, now find the midpoint value in the original container and
  // return that iterator.
  ForwardIterator median = find(first,last,*midpoint);

  return median;
}
@}

@d \verb|recorder| output operator 
@{friend ostream& operator<< (ostream& out, 
   	                    const recorder<Counter>&rhs) {

  typedef typename counter_vector<Counter>::const_iterator cvi;

  if (rhs.show_median) {  
    out << "MEDIAN" << endl << "======" << endl;
    rhs.report(out, &median_element<cvi>);
  }	

  if (rhs.show_min) {  
    out << "MIN" << endl << "===" << endl;
    rhs.report(out, &min_element<cvi>);
  }

  if (rhs.show_max) {
    out << "MAX" << endl << "===" << endl;
    rhs.report(out, &max_element<cvi>);
  }

  return out;
}
@}

@D \verb|recorder| 
@{template <class Counter>
class recorder {

  @<\verb|recorder| counter map@>
  @<\verb|recorder| snapshot data@>

  @<\verb|recorder| print string declaration@>
  @<\verb|recorder| registry of all counters declaration@>

  @<\verb|recorder| output operator@>

 public:
  @<counter index enumeration@>

  @<\verb|recorder| constructor@>

  @<\verb|recorder| \verb|pause()| method@>
  @<\verb|recorder| \verb|resume()| method@>
  @<\verb|recorder| \verb|record()| method@>
  @<\verb|recorder| \verb|reset()| method@>

  @<\verb|recorder| \verb|insert()| method@>

  // control over which operations are reported
  @<\verb|recorder| \verb|report_init()| method@>
  @<\verb|recorder| \verb|op_filter| definition@>
  @<\verb|recorder| \verb|show_all_ops()| method@>
  @<\verb|recorder| \verb|hide_all_ops()| method@>
  @<\verb|recorder| \verb|show_op()| method@>
  @<\verb|recorder| \verb|show_op()| sequence method@>
  @<\verb|recorder| \verb|hide_op()| method@>
  @<\verb|recorder| \verb|show_op(bool)| method@>
 
  // control over which counts are reported
  @<\verb|recorder| \verb|show_| count flags@>
  @<\verb|recorder| \verb|show_min_counts()| method@>
  @<\verb|recorder| \verb|show_max_counts()| method@>
  @<\verb|recorder| \verb|show_mean_counts()| method@>
  @<\verb|recorder| \verb|show_median_counts()| method@>
  @<\verb|recorder| \verb|show_all_counts()| method@>
  @<\verb|recorder| \verb|show_zero_counts()| method@>

  @<\verb|recorder| \verb|report()| method@>
  @<\verb|recorder| \verb|report_headings()| method@>
  @<\verb|recorder| \verb|report_table()| method@>
  @<\verb|recorder| \verb|report_totals()| method@>
};

@<\verb|recorder| print string definition@>

@<\verb|recorder| registry of all counters definition@>
@}

\section{Evaluators}

\subsection{Options}

The behavior of either output format can be customized with the
following option settings.

\subsubsection{Operator Options}

By default, all operators are included in the output of the reporting
functions. 

Defaults are set by the \verb|report_init| function, which is called
by the \verb|recorder| constructor.

@d \verb|recorder| \verb|report_init()| method 
@{void report_init() {
  show_all_ops();
  show_min = false;
  show_max = false;
  show_mean = false;
  show_median = true;
  show_all = false;
  show_zero = false;
}
@}

Each of the counted operations is selectively shown or hidden in the
output based upon the values of this array.

@d \verb|recorder| \verb|op_filter| definition 
@{   bool op_filter[NCOUNTERS];
@}

This array is manipulated with the following functions:

\begin{itemize}

\item {\bf Show all Operators}

@d \verb|recorder| \verb|show_all_ops()| method 
@{void show_all_ops() {
  for (size_t i = 0; i < NCOUNTERS; ++i)
    op_filter[i] = true;
}

void hide_no_ops() { show_all_ops(); }
@}

\item {\bf Hide all Operators}

@d \verb|recorder| \verb|hide_all_ops()| method 
@{void hide_all_ops() {
  for (size_t i = 0; i < NCOUNTERS; ++i)
    op_filter[i] = false;
}

void show_no_ops() { hide_all_ops(); }
@}

\item {\bf Show an Operator}

@d \verb|recorder| \verb|show_op()| method 
@{void show_op(operator_type op) {
   show_op(op,true);
}
@}

\item {\bf Show or Hide an Operator}

@d \verb|recorder| \verb|show_op(bool)| method 
@{void show_op(operator_type op, bool state) {
    op_filter[op] = state;  
}
@}

\item {\bf Hide an Operator}

@d \verb|recorder| \verb|hide_op()| method 
@{void hide_op(operator_type op) {
   show_op(op,false);
}
@}

\item {\bf Container of Bools}

Another useful option is to pass in a pair of iterators over a
container of bools representing whether or not to show each operation.

@d \verb|recorder| \verb|show_op()| sequence method 
@{template <class InputIterator>
void show_op (InputIterator begin, InputIterator end) {
  for (operator_type op = 0; begin != end; ++op)
    show_op(op, *begin);
}
@}

\end{itemize}

\subsubsection{Count Options}

The default is to show the median.  For a good discussion of why this
is a useful choice see \cite{musser:timing}.

We use some simple boolean flags to track what will be done.

@d \verb|recorder| \verb|show_| count flags 
@{bool show_min, show_max, show_mean, show_median, show_all,
     show_zero;
@}

\begin{itemize}
\item {\bf Include Minimum Counts from the Recorded Iterations}
@d \verb|recorder| \verb|show_min_counts()| method 
@{void show_min_counts(bool b) {
   show_min = b;
}

void show_min_counts() { show_min_counts(true); }
@}

\item {\bf Include Maximum Counts from the Recorded Iterations}
@d \verb|recorder| \verb|show_max_counts()| method 
@{void show_max_counts(bool b) {
   show_max = b;
}

void show_max_counts() { show_max_counts(true); }
@}

\item {\bf Include Mean Counts from the Recorded Iterations}
@d \verb|recorder| \verb|show_mean_counts()| method 
@{void show_mean_counts(bool b) {
   show_mean = b;
}

void show_mean_counts() { show_mean_counts(true); }
@}

\item {\bf Include Median Counts from the Recorded Iterations}
@d \verb|recorder| \verb|show_median_counts()| method 
@{void show_median_counts(bool b) {
   show_median = b;
}

void show_median_counts() { show_median_counts(true); }
@}

\item {\bf Include All Counts from the Recorded Iterations}
@d \verb|recorder| \verb|show_all_counts()| method 
@{void show_all_counts(bool b) {
   show_all = b;
}

void show_all_counts() { show_all_counts(true); }
@}

\item {\bf include zero count results}
@d \verb|recorder| \verb|show_zero_counts()| method 
@{void show_zero_counts(bool b) {
   show_zero = b;
}

void show_zero_counts() { show_zero_counts(true); }
@}

% \item {\bf total/accumulate all iterations}

\end{itemize}

\section{Counting Adaptors}

\label{sec:adaptor-reference}
There are a number of conventions that should be followed when writing
a counting adaptor to work with the \verb|recorder| class.  

All counting adaptors should take three template parameters: a name to
be used in reports\footnote{Actually, the name parameter should be
declared using the {\tt COUNTERS\_NAME\_} macros, because some
compilers can not handle the name parameter at all (see section
\ref{sec:des:print_name}, page \pageref{sec:des:print_name} and
section \ref{sec:des:print_name_bug}, page
\pageref{sec:des:print_name_bug}).}, and the type being adapted.

The operations counts themselves should be stored in a \verb|counter_vector|.
The anonymous enumeration described in section \ref{sec:src:enum}, page
\pageref{sec:src:enum}, should be used for the vector's indices.

@d declare and register counters 
@{static counter_vector<Counter> counters;
@}

The \verb|counter_vector| automatically registers itself with the
\verb|recorder|'s registry when it its constructor is called.

The \verb|counter_vector| should be statically initialized as follows
(this is from the \verb|unary_function_counter|, other counters should
be nearly identical):

@d \verb|unary_function_counter| counter variable definition 
@{template <class AdaptableUnaryFunction, 
          COUNTERS_NAME_DECL
          class Counter>
counter_vector<Counter> 
unary_function_counter<AdaptableUnaryFunction, 
                       COUNTERS_NAME_PARM
                       Counter>::
counters(COUNTERS_NAME_TEST ? 
             "unary_function_counter" : "", 
	 NCOUNTERS);
@}

The \verb|COUNTERS_NAME_| macros are described in more detail in
section \ref{sec:src:print_name_bug}, page
\pageref{sec:src:print_name_bug}.

Another variable that any counter adaptor should include is
\verb|generation|, defined as follows:

@d declare generation 
@{Counter generation;
@}

Any constructors for the counter should initialize \verb|generation|
to 1.  The intent behind \verb|generation| is much like the
conventional meaning of the term.  A copy of an object can be
considered a child or a new generation.  

Thus the non-copy constructors correspond to the first generation of
an object.  Each copy constructor invocation increases generation by 1.  
Note that the generation is kept on a per-object basis, unlike the
\verb|counter_vector|, which is \verb|static|, and therefore shared
among all counter adaptors of that type.  

A copy constructor should set the \verb|counter_vector[GENERATION]| to
its generation if it is larger than
\verb|counter_vector[GENERATION]|'s current value.  It is not useful
to accumulate the generation itself, since that would simply represent
a total of all constructor calls.  That information is already available.

Counting other operations is mostly straightforward.  In general the
function should increment the appropriate counter and call the adapted
class's implementation. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Iterator Counting Adaptor}

As is true for all counting adaptors, there are template parameters to
specify the adapted type, a printable name and the type of the counter
itself.  The latter two have default values.

There is one additional parameter that allows the user to specify the
\verb|difference_type| of the counting iterator.  By default this is
the \verb|difference_type| of the base iterator, adapted for counting.
Specifying the type explicitly allows control over the type's
printable name and its counter type.

@d \verb|iterator_counter| template parameter list 
@{template <class Iterator,
	  class Difference = 
	      difference_counter<typename iterator_traits<Iterator>
                                          ::difference_type, 
                                 Iterator>,
          COUNTERS_NAME_DECL_DEFAULT
          class Counter = DEFAULT_COUNTER_TYPE>
@}

@d \verb|iterator_counter| typedef for \verb|iterator_traits| 
@{  typedef typename iterator_traits<Iterator>::iterator_category
          iterator_category;
  typedef typename iterator_traits<Iterator>::value_type
          value_type;
  typedef Difference difference_type;
  typedef typename iterator_traits<Iterator>::pointer pointer;
  typedef typename iterator_traits<Iterator>::reference reference;
@}


To simplify further declarations within this class, the type definition
\verb|self| is defined as follows:

@d \verb|iterator_counter| typedef self 
@{   typedef iterator_counter<Iterator, Difference, 
                            COUNTERS_NAME_PARM
                            Counter>
           self;
@}

Since operations must be declared to work on different combinations of
adapted and unadapted iterators, additional types are declared to
simplify these definitions.

@d \verb|iterator_counter| typedef for operations 
@{  typedef Iterator UnadaptedIterator;
  typedef typename iterator_traits<Iterator>::difference_type
          UnadaptedDifference;
  typedef Difference AdaptedDifference;
@}

%%  static variable definitions  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The counter vector is defined below, initializing the printable name
based on the template parameter.

@d \verb|iterator_counter| counter variable definition 
@{template <class Iterator, class Difference, 
          COUNTERS_NAME_DECL
          class Counter>
counter_vector<Counter>
iterator_counter<Iterator, Difference, 
                 COUNTERS_NAME_PARM
                 Counter>::
counters(COUNTERS_NAME_TEST ?
            "iterator_counter" : "", 
	 NCOUNTERS);
@}


%%  default constructor  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
The default constructor sets the generation to 1.

@d \verb|iterator_counter| default constructor 
@{iterator_counter () : //base_iterator(), 
                      generation(1) {
  ++counters[DEFAULT_CTOR];
}
@}

%%  copy constructor  %%
%%%%%%%%%%%%%%%%%%%%%%%%

The copy constructor takes the generation and increments it by one.
If this is now the highest generation, it is set to the counter.

@d \verb|iterator_counter| copy constructor 
@{iterator_counter (const self& x)
     : base_iterator(x.base_iterator),
       generation(x.generation + 1) {
  ++counters[COPY_CTOR];
  counters[GENERATION] = max(counters[GENERATION], generation);
}
@}

@d \verb|iterator_counter| destructor 
@{~iterator_counter () { ++counters[DTOR]; }
@}

%%  external constructor  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In adddition to the default constructor and the copy constructor there is a 
constructor which takes an object of the adapted iterator class as an
argument.  This is necessary for some iterator classes which call
special constructors.  For example, a back insert iterator takes a
container as an argument of its constructor. This external constructor
is called first and then the resulting iterator object is given to the counting
adapter with this constructor. If any other operation is called, befor the
iterator object is given to the counting adaptor, that operation won't be counted.

@d \verb|iterator_counter| external constructor 
@{iterator_counter (const Iterator& x) : base_iterator(x),
                                       generation(1) {
  ++counters[OTHER_CTOR];
}
@}

%%  base ()  %%
%%%%%%%%%%%%%%%
The method \verb|base| gives the the base iterator back.
@d \verb|iterator_counter| base 
@{Iterator& base () {
  ++counters[BASE];
  return base_iterator;
}
@}

%%  uncounted constructor  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Some of the counting adaptor's member functions need to call a constructor.
In this case, this invocation of the constructor should not be counted.
However, the generation should be kept.  The following private
constructor is provided for this purpose.

@d \verb|iterator_counter| uncounted constructor 
@{iterator_counter (const self& x,
                  const bool count)

: base_iterator(x.base_iterator),
  generation(x.generation)
{
  if (count) {
    ++counters[COPY_CTOR];
  }
}

iterator_counter (const Iterator& x,
                  const Counter gen,
                  const bool count) : base_iterator(x),
                                      generation(gen) {
  if (count) {
    ++counters[OTHER_CTOR];
  }
}
@}

%%  assignment %%
%%%%%%%%%%%%%%%%%
The assignment makes a copy.  The generation isn't increased.
@d \verb|iterator_counter operator=| , assignment
@{self& operator= (const self& y) {
  ++counters[ASSIGNMENT];
  base_iterator = y.base_iterator;
  return *this;
}
@}

%% equality %%
%%%%%%%%%%%%%%
@d \verb|iterator_counter operator==|, equal
@{friend bool operator== (const self& x, const self& y) {
  ++self::counters[EQUALITY];
  return (x.base_iterator == y.base_iterator);
}
@}

%% less %%
%%%%%%%%%%
@d \verb|iterator_counter operator<| , less
@{friend bool operator< (const self& x, const self& y) {
  ++self::counters[LESS_THAN];
  return (x.base_iterator < y.base_iterator);
}
@}


@d \verb|iterator_counter operator*| , dereference
@{reference operator* () const {
  ++counters[DEREFERENCE];
  return *base_iterator;
}
@}

@d \verb|iterator_counter operator++|, preincrement
@{self& operator++ () {
  ++counters[PRE_INCREMENT];
  ++base_iterator;
  return *this;
}
@}

@d \verb|iterator_counter operator++|, postincrement
@{self operator++ (int) {
  self return_value (*this, false);
  ++counters[POST_INCREMENT];
  base_iterator++;
  return self(return_value, false);
}
@}

@d \verb|iterator_counter operator--|, predecrement
@{self& operator-- () {
  ++counters[PRE_DECREMENT];
  --base_iterator;
  return *this;
}
@}

@d \verb|iterator_counter operator--|, postdecrement
@{self operator-- (int) {
  self return_value (*this, false);
  ++counters[POST_DECREMENT];
  base_iterator--;
  return self(return_value, false);
}
@}

@d \verb|iterator_counter operator<<|, ostream
@{friend ostream& operator<< (ostream& o, const self& n) {
  return o << n.base_iterator;
}
@}


%%  put parts together  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%

@D \verb|iterator_counter| 
@{@<\verb|iterator_counter| template parameter list@>

class iterator_counter {

  @<\verb|iterator_counter| typedef for \verb|iterator_traits|@>
  @<\verb|iterator_counter| typedef self@>
  @<\verb|iterator_counter| typedef for operations @>

  @<counter index enumeration@>
  @<declare and register counters@>

  Iterator base_iterator;
  @<declare generation@>

  @<\verb|iterator_counter| uncounted constructor@>

 public:
  @<\verb|iterator_counter| default constructor@>
  @<\verb|iterator_counter| copy constructor@>
  @<\verb|iterator_counter| destructor@>
  @<\verb|iterator_counter| external constructor@>
  @<\verb|iterator_counter| base@>

  @<\verb|iterator_counter operator=| , assignment@>
  @<\verb|iterator_counter operator==|, equal@>
  @<\verb|iterator_counter operator<| , less@>
  @<\verb|iterator_counter operator*| , dereference@>
  @<\verb|iterator_counter operator++|, preincrement@>
  @<\verb|iterator_counter operator++|, postincrement@>
  @<\verb|iterator_counter operator--|, predecrement@>
  @<\verb|iterator_counter operator--|, postdecrement@>
  @<\verb|iterator_counter operator+| , addition, case 4@>
  @<\verb|iterator_counter operator+| , addition, case 6@>
  @<\verb|iterator_counter operator+| , addition, case 7@>
  @<\verb|iterator_counter operator+| , addition, case 9@>
  @<\verb|iterator_counter operator+=|, addition assign, case 4@>
  @<\verb|iterator_counter operator+=|, addition assign, case 6@>
  @<\verb|iterator_counter operator-| , subtraction, case 4@>
  @<\verb|iterator_counter operator-| , subtraction, case 6@>
  @<\verb|iterator_counter operator-| , subtraction, case 7@>
  @<\verb|iterator_counter operator-| , subtraction, case 8@>
  @<\verb|iterator_counter operator-| , subtraction, case 9@>
  @<\verb|iterator_counter operator-=|, subtraction assign, case 4@>
  @<\verb|iterator_counter operator-=|, subtraction assign, case 6@>
  @<\verb|iterator_counter operator[]|, subscripton, case 1@>
  @<\verb|iterator_counter operator[]|, subscripton, case 2@>

  @<\verb|iterator_counter operator<<|, ostream@>

};

@<\verb|iterator_counter| counter variable definition @>
@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Difference Type Counting Adaptor}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@d \verb|difference_counter| template parameter list 
@{template <class Difference,
          class Iterator,
          COUNTERS_NAME_DECL_DEFAULT
          class Counter = DEFAULT_COUNTER_TYPE>
@}


To simplify further declarations within this class, the type definition
\verb|self| is defined as follows:

@d \verb|difference_counter| typedef self 
@{   typedef difference_counter<Difference, Iterator, 
                              COUNTERS_NAME_PARM
                              Counter>
            self;


   typedef typename iterator_traits<Iterator>::reference
      reference;
@}

Since operations must be declared to work on different combinations of
adapted and unadapted iterators, additional types are declared to
simplify these definitions.

@d \verb|difference_counter| typedef for operations 
@{
  typedef Iterator UnadaptedIterator;

  typedef Difference UnadaptedDifference;
@}

%%  static variable definitions  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@d \verb|difference_counter| counter variable definition 
@{template <class Difference, class Iterator, 
          COUNTERS_NAME_DECL
          class Counter>
counter_vector<Counter> 
difference_counter<Difference, Iterator, 
                   COUNTERS_NAME_PARM
                   Counter>::
counters(COUNTERS_NAME_TEST ? 
             "difference_counter" : "", 
	 NCOUNTERS);
@}

%%  Overview of Operation  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%The \verb|difference_type| provides the operations shown in the
%following table.   Some these operations, which involve the class
%iterator, implemented in the
%% forced line-break due to overfull hbox
%\\\verb|iterator_counter| class.

%\begin{tabular}{|l|l|l|l|}                                                                \hline
%                              & Expression        & Return    & Defined in Concept     \\
%                              &                   & Type      &                        \\ \hline
%Default constructor           & \verb|N()|        & N         & Default Constructible  \\
%                              & \verb|N n;|       &           &                        \\ \hline
%Copy constructor              & \verb|N(o)|       & N         & Assignable             \\
%                              & \verb|N n(o);|    &           &                        \\         
%                              & \verb|N n = o;|   &           &                        \\ \hline
%Conversion                    & \verb|int(n)|     & int       &                        \\ \hline
%Assignment                    & \verb|n = o|      & \verb|N&| & Assignable             \\ \hline
%Swap                          & \verb|swap (n,o)| & void      & Assignable             \\ \hline
%Equality                      & \verb|n == o|     & B         & Equality Comparable    \\ \hline
%Inequality                    & \verb|n != o|     & B         & Equality Comparable    \\ \hline
%Less                          & \verb|n < o|      & B         & LessThan Comparable    \\ \hline
%Greater                       & \verb|n > o|      & B         & LessThan Comparable    \\ \hline
%Less or equal                 & \verb|n <= o|     & B         & LessThan Comparable    \\ \hline
%Greater or equal              & \verb|n >= o|     & B         & LessThan Comparable    \\ \hline
%Preincrement                  & \verb|++n|        & N         &                        \\ \hline
%Postincrement                 & \verb|n++|        & N         &                        \\ \hline
%Predecrement                  & \verb|--n|        & N         &                        \\ \hline
%Postdecrement                 & \verb|n--|        & N         &                        \\ \hline
%Addition                      & \verb|n + o|      & N         &                        \\
%                              & \verb|i + n|      & I         &                        \\
%                              & \verb|n + i|      & I         &                        \\
%                              & \verb|n += o|     & N         &                        \\
%                              & \verb|i += n|     & I         &                        \\ \hline
%Subtraction                   & \verb|n - o|      & N         &                        \\
%                              & \verb|i - n|      & I         &                        \\
%                              & \verb|n -= o|     & N         &                        \\
%                              & \verb|i -= n|     & I         &                        \\ \hline
%Multiplication                & \verb|n * o|      & N         &                        \\
%                              & \verb|n *= o|     & N         &                        \\ \hline
%Division                      & \verb|n / o|      & N         &                        \\
%                              & \verb|n /= o|     & N         &                        \\ \hline
%\end{tabular}

%\begin{tabular}{ll}
%N        & class \verb|difference_type|           \\
%n,o      & object of class \verb|difference_type| \\
%I        & class iterator                         \\
%i,j      & object of class iterator               \\
%B        & convertable to boolean                 \\
%\end{tabular}


%%  default constructor  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
All constructors have to register the counters. The default constructor sets
the generation to 1.

@d \verb|difference_counter| default constructor 
@{difference_counter () : //base_difference(),
                        generation(1) {
  ++counters[DEFAULT_CTOR];
}
@}

%%  copy constructor  %%
%%%%%%%%%%%%%%%%%%%%%%%%

%%!!
The copy constructor takes the generation and increments it by one.  If this is
now the highest generation, then it is set to the counter.

@d \verb|difference_counter| copy constructor 
@{difference_counter (const self& x)
: base_difference(x.base_difference),
  generation(x.generation + 1)
{
  ++counters[COPY_CTOR];
  counters[GENERATION] = max(counters[GENERATION], generation);
}
@}

@d \verb|difference_counter| destructor 
@{~difference_counter () { ++counters[DTOR]; }
@}

%%  external constructor  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In adddition to the default constructor and the copy constructor there
is a constructor which takes an object of the adapted iterator class
as an argument.  This is necessary for some iterator classes which
call special constructors.  For example, a back insert iterator takes
a container as an argument of its constructor. This external
constructor is called first and then the resulting object is given to
the counting adapter with this constructor.

@d \verb|difference_counter| external constructor 
@{difference_counter (const Difference& x) : base_difference(x),
                                           generation(1) {
  ++counters[OTHER_CTOR];
}
@}

%%  uncounted constructor  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Some of the counting adaptor's member functions need to call a constructor.
In this case, this invocation of the constructor shoud not be counted.
However, the generation should be kept.  The following private
constructor is provided for this purpose.

@d \verb|difference_counter| uncounted constructor 
@{difference_counter (const self& x, const bool count)
     : base_difference(x.base_difference),
       generation(x.generation)
{
  if (count) {
    ++counters[COPY_CTOR];
  }
}

difference_counter (const Difference& x, const Counter gen,
                    const bool count)
     : base_difference(x), generation(gen) {
  if (count) {
    ++counters[OTHER_CTOR];
  }
}
@}

%% conversion %%
%%%%%%%%%%%%%%%%
@d \verb|difference_counter| int(), conversion
@{operator int() const {
  ++counters[CONVERSION];
  return int(base_difference);
}
@}

%% base() %%
%%%%%%%%%%%%
With the operation base is it possible to get the base value.
@d \verb|difference_counter| base() 
@{Difference base() const {
  ++counters[BASE];
  return base_difference;
}
@}

%% base() %%
%%%%%%%%%%%%
The operation base is used by the \verb|iterator_counter| and is not
counted.
@d \verb|difference_counter| uncounted base() 
@{Difference base(const bool count) const {
  if (count)
     ++counters[BASE];  
  return base_difference;
}
@}

%%  assignment %%
%%%%%%%%%%%%%%%%%
The assignment makes a copy. The generation isn't increased.
@d \verb|difference_counter operator=| , assignment
@{self& operator= (const self& y) {
  ++counters[ASSIGNMENT];
  base_difference = y.base_difference;
  return *this;
}
@}

@d \verb|difference_counter operator==|, equal
@{friend bool operator== (const self& x, const self& y) {
  ++self::counters[EQUALITY];
  return (x.base_difference == y.base_difference);
}
friend bool operator== (const self& x, const Difference& y) {
  ++self::counters[EQUALITY];
  return (x.base_difference == y);
}
friend bool operator== (const Difference& x, const self& y) {
  ++self::counters[EQUALITY];
  return (x == y.base_difference);
}
@}

@d \verb|difference_counter operator<| , less
@{friend bool operator< (const self& x, const self& y) {
  ++self::counters[LESS_THAN];
  return (x.base_difference < y.base_difference);
}
friend bool operator< (const self& x, const Difference& y) {
  ++self::counters[LESS_THAN];
  return (x.base_difference < y);
}
friend bool operator< (const Difference& x, const self& y) {
  ++self::counters[LESS_THAN];
  return (x < y.base_difference);
}
@}

@d \verb|difference_counter operator++|, preincrement
@{self& operator++ () {
  ++counters[PRE_INCREMENT];
  ++base_difference;
  return *this;
}
@}

@d \verb|difference_counter operator++|, postincrement
@{self operator++ (int) {
  self return_value (*this, false);
  ++counters[POST_INCREMENT];
  base_difference++;
  return self(return_value, false);
}
@}

@d \verb|difference_counter operator--|, predecrement
@{self& operator-- () {
  ++counters[PRE_DECREMENT];
  --base_difference;
  return *this;
}
@}

@d \verb|difference_counter operator--|, postdecrement
@{self operator-- (int) {
  self return_value (*this, false);
  ++counters[POST_DECREMENT];
  base_difference--;
  return self(return_value, false);
}
@}

@d \verb|difference_counter operator<<|, left shift 
@{self operator<< (int x) const {
  ++counters[LEFT_SHIFT];
  return self(base_difference << x, false);
}
@}

@d \verb|difference_counter operator>>|, right shift 
@{self operator>> (int x) const {
  ++counters[RIGHT_SHIFT];
  return self(base_difference >> x, false);
}
@}

@d \verb|difference_counter operator<<=|, left shift assign 
@{self& operator<<= (int x) {
  ++counters[LEFT_SHIFT_ASSIGN];
  base_difference <<= x;
  return *this;
}
@}

@d \verb|difference_counter operator>>=|, right shift assign 
@{self& operator>>= (int x) {
  ++counters[RIGHT_SHIFT_ASSIGN];
  base_difference >>= x;
  return *this;
}
@}

%% multiply %%
%%%%%%%%%%%%%%
The multiplication operation is broken into three cases:

\begin{tabular}{|l|l|l|l|l|}                                            \hline
expr         & argument               & ret type    & counted & case \\ \hline
\verb|n * n| & difference, difference & difference  & no      &      \\
             & AdaptDiff,  difference & AdaptDiff   & yes     & 1    \\
             & difference, AdaptDiff  & AdaptDiff   & yes     & 2    \\
             & AdaptDiff,  AdaptDiff  & AdaptDiff   & yes     & 3    \\ \hline
\end{tabular}

@d \verb|difference_counter operator*| , multiply, case 1
@{self operator* (const UnadaptedDifference& y) const {
  ++counters[TIMES];
  return self(base_difference * y, generation, false);
}
@}

@d \verb|difference_counter operator*| , multiply, case 2
@{
friend self operator* (const UnadaptedDifference& x,
                       const self& y) {
  ++counters[TIMES];
  return self(x * y.base_difference, y.generation, false);
}
@}

@d \verb|difference_counter operator*| , multiply, case 3
@{self operator* (const self& y) const {
  ++counters[TIMES];
  return self(base_difference * y.base_difference,
              max(generation, y.generation), false);
}
@}

%% multiply assignment %%
%%%%%%%%%%%%%%%%%%%%%%%%%
The multiplication assignment operation is broken into three cases:

\begin{tabular}{|l|l|l|l|l|}                                             \hline
expr          & argument               & ret type    & counted & case \\ \hline
\verb|n *= n| & difference, difference & difference  & no      &      \\
              & AdaptDiff,  difference & AdaptDiff   & yes     & 1    \\
              & difference, AdaptDiff  & difference  & yes     & 2    \\
              & AdaptDiff,  AdaptDiff  & AdaptDiff   & yes     & 3    \\ \hline
\end{tabular}

@d \verb|difference_counter operator*=|, multiply assign, case 1
@{self& operator*= (const UnadaptedDifference& y) {
  ++counters[TIMES_ASSIGN];
  base_difference *= y;
  return *this;
}
@}

@d \verb|difference_counter operator*=|, multiply assign, case 2
@{friend UnadaptedDifference& operator*= (UnadaptedDifference& x,
                                    const self& y) {
  ++counters[TIMES_ASSIGN];
  x *= y.base_difference;
  return x;
}
@}

@d \verb|difference_counter operator*=|, multiply assign, case 3
@{self& operator*= (const self& y) {
  ++counters[TIMES_ASSIGN];
  base_difference *= y.base_difference;
  generation = max(generation, y.generation);
  return *this;
}
@}

%% divide %%
%%%%%%%%%%%%
The division operation is broken into three cases:

\begin{tabular}{|l|l|l|l|l|}                                            \hline
expr         & argument               & ret type    & counted & case \\ \hline
\verb|n / n| & difference, difference & difference  & no      &      \\
             & AdaptDiff,  difference & AdaptDiff   & yes     & 1    \\
             & difference, AdaptDiff  & AdaptDiff   & yes     & 2    \\
             & AdaptDiff,  AdaptDiff  & AdaptDiff   & yes     & 3    \\ \hline
\end{tabular}

@d \verb|difference_counter operator/| , divide, case 1
@{self operator/ (const UnadaptedDifference& y) const {
  ++counters[DIVIDE];
  return self(base_difference / y, generation, false);
}
@}

@d \verb|difference_counter operator/| , divide, case 2
@{
friend self operator/ (const UnadaptedDifference& x,
                       const self& y) {
  ++counters[DIVIDE];
  return self(x / y.base_difference, y.generation, false);
}
@}

@d \verb|difference_counter operator/| , divide, case 3
@{self operator/ (const self& y) const {
  ++counters[DIVIDE];
  return self(base_difference / y.base_difference,
              max(generation, y.generation), false);
}
@}

%% divide assignment %%
%%%%%%%%%%%%%%%%%%%%%%%
The division assignment operation is broken into three cases:

\begin{tabular}{|l|l|l|l|l|}                                             \hline
expr          & argument               & ret type    & counted & case \\ \hline
\verb|n /= n| & difference, difference & difference  & no      &      \\
              & AdaptDiff,  difference & AdaptDiff   & yes     & 1    \\
              & difference, AdaptDiff  & difference  & yes     & 2    \\
              & AdaptDiff,  AdaptDiff  & AdaptDiff   & yes     & 3    \\ \hline
\end{tabular}

@d \verb|difference_counter operator/=|, divide assign, case 1
@{self& operator/= (const UnadaptedDifference& y) {
  ++counters[DIVIDE_ASSIGN];
  base_difference /= y;
  return *this;
}
@}

@d \verb|difference_counter operator/=|, divide assign, case 2
@{friend UnadaptedDifference& operator/= (UnadaptedDifference& x,
                                    const self& y) {
  ++counters[DIVIDE_ASSIGN];
  x /= y.base_difference;
  return x;
}
@}

@d \verb|difference_counter operator/=|, divide assign, case 3
@{self& operator/= (const self& y) {
  ++counters[DIVIDE_ASSIGN];
  base_difference /= y.base_difference;
  generation = max(generation, y.generation);
  return *this;
}
@}

%% put parts together %%
%%%%%%%%%%%%%%%%%%%%%%%%%

@D \verb|difference_counter| 
@{@<\verb|difference_counter| template parameter list@>
class difference_counter {

  @<\verb|difference_counter| typedef self@>
  @<\verb|difference_counter| typedef for operations @>

  @<counter index enumeration@>
  @<declare and register counters@>

  Difference base_difference;
  @<declare generation@>

public:
  @<\verb|difference_counter| uncounted constructor@>
  @<\verb|difference_counter| uncounted base()@>

public:
  @<\verb|difference_counter| default constructor@>
  @<\verb|difference_counter| copy constructor@>
  @<\verb|difference_counter| destructor@>
  @<\verb|difference_counter| external constructor@>
  @<\verb|difference_counter| int(), conversion@>
  @<\verb|difference_counter| base() @>

  @<\verb|difference_counter operator=| , assignment@>
  @<\verb|difference_counter operator==|, equal@>
  @<\verb|difference_counter operator<| , less@>
  @<\verb|difference_counter operator++|, preincrement@>
  @<\verb|difference_counter operator++|, postincrement@>
  @<\verb|difference_counter operator--|, predecrement@>
  @<\verb|difference_counter operator--|, postdecrement@>
  @<\verb|difference_counter operator<<|, left shift@>
  @<\verb|difference_counter operator>>|, right shift@>
  @<\verb|difference_counter operator<<=|, left shift assign@>
  @<\verb|difference_counter operator>>=|, right shift assign@>
  @<\verb|difference_counter operator+| , addition, case 1@>
  @<\verb|difference_counter operator+| , addition, case 2@>
  @<\verb|difference_counter operator+| , addition, case 3@>
  @<\verb|difference_counter operator+| , addition, case 5@>
  @<\verb|difference_counter operator+| , addition, case 8@>
  @<\verb|difference_counter operator+=|, addition assign, case 1@>
  @<\verb|difference_counter operator+=|, addition assign, case 2@>
  @<\verb|difference_counter operator+=|, addition assign, case 3@>
  @<\verb|difference_counter operator+=|, addition assign, case 5@>
  @<\verb|difference_counter operator-| , subtraction, case 1@>
  @<\verb|difference_counter operator-| , subtraction, case 2@>
  @<\verb|difference_counter operator-| , subtraction, case 3@>
  @<\verb|difference_counter operator-| , subtraction, case 5@>
  @<\verb|difference_counter operator-=|, subtraction assign, case 1@>
  @<\verb|difference_counter operator-=|, subtraction assign, case 2@>
  @<\verb|difference_counter operator-=|, subtraction assign, case 3@>
  @<\verb|difference_counter operator-=|, subtraction assign, case 5@>
  @<\verb|difference_counter operator*| , multiply, case 1@>
  @<\verb|difference_counter operator*| , multiply, case 2@>
  @<\verb|difference_counter operator*| , multiply, case 3@>
  @<\verb|difference_counter operator*=|, multiply assign, case 1@>
  @<\verb|difference_counter operator*=|, multiply assign, case 2@>
  @<\verb|difference_counter operator*=|, multiply assign, case 3@>
  @<\verb|difference_counter operator/| , divide, case 1@>
  @<\verb|difference_counter operator/| , divide, case 2@>
  @<\verb|difference_counter operator/| , divide, case 3@>
  @<\verb|difference_counter operator/=|, divide assign, case 1@>
  @<\verb|difference_counter operator/=|, divide assign, case 2@>
  @<\verb|difference_counter operator/=|, divide assign, case 3@>
};

@<\verb|difference_counter| counter variable definition @>
@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Mixed Operations on Iterator and Difference Types}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The following operations involve operations between \verb|iterator|
and
% forced line-break due to overfull hbox
\\\verb|difference_type| arguments.

%% addition overview %%
%%%%%%%%%%%%%%%%%%%%%%%
The addition assignment operation is broken into nine cases:

\begin{tabular}{|l|l|l|l|l|}                                                           \hline
expr         & argument               & ret type    & counted in                &   \\ \hline
\verb|n + o| & Difference, Difference & Difference  & -                         &   \\
             & AdaptDiff, Difference  & AdaptDiff   & \verb|difference_counter| & 1 \\
             & Difference, AdaptDiff  & AdaptDiff   & \verb|difference_counter| & 2 \\
             & AdaptDiff, AdaptDiff   & AdaptDiff   & \verb|difference_counter| & 3 \\ \hline
\verb|i + n| & Iterator, Difference   & Iterator    & -                         &   \\
             & AdaptIter, Difference  & AdaptIter   & \verb|iterator_counter|   & 4 \\
             & Iterator, AdaptDiff    & Iterator    & \verb|difference_counter| & 5 \\
             & AdaptIter, AdaptDiff   & AdaptIter   & \verb|iterator_counter|   & 6 \\ \hline
\verb|d + n| & Difference, Iterator   & Iterator    & -                         &   \\
             & Difference, AdaptIter  & AdaptIter   & \verb|iterator_counter|   & 7 \\
             & AdaptDiff, Iterator    & Iterator    & \verb|difference_counter| & 8 \\
             & AdaptDiff, AdaptIter   & AdaptIter   & \verb|iterator_counter|   & 9 \\ \hline
\end{tabular}

\begin{tabular}{ll}
n, o  & object of class \verb|difference_type| \\
i     & object of class iterator               \\
\end{tabular}

%% addition case 1 %%
%%%%%%%%%%%%%%%%%%%%%
@d \verb|difference_counter operator+| , addition, case 1
@{self operator+ (const UnadaptedDifference& y) const {
  ++counters[PLUS];
  return self(base_difference + y, generation, false);
}
@}

%% addition case 2 %%
%%%%%%%%%%%%%%%%%%%%%
@d \verb|difference_counter operator+| , addition, case 2
@{friend self operator+ (const UnadaptedDifference& x,
                       const self& y) {
  ++self::counters[PLUS];
  return self(x + y.base_difference, y.generation, false);
}
@}

%% addition case 3 %%
%%%%%%%%%%%%%%%%%%%%%
@d \verb|difference_counter operator+| , addition, case 3
@{self operator+ (const self& y) const {
  ++counters[PLUS];
  return self(base_difference + y.base_difference,
              max(generation, y.generation), false);
}
@}

%% addition case 4 %%
%%%%%%%%%%%%%%%%%%%%%
@d \verb|iterator_counter operator+| , addition, case 4
@{self operator+(const UnadaptedDifference& n) const {
  ++counters[PLUS];
  return self(base_iterator + n, generation, false);
}
@}

%% addition case 5 %%
%%%%%%%%%%%%%%%%%%%%%
@d \verb|difference_counter operator+| , addition, case 5
@{friend Iterator operator+ (const UnadaptedIterator& i,
                           const self& n) {
  ++self::counters[PLUS];
  return Iterator(i + n.base_difference);
}
@}

%% addition, case 6 %%
%%%%%%%%%%%%%%%%%%%%%%
@d \verb|iterator_counter operator+| , addition, case 6
@{self operator+(const AdaptedDifference& n) const {
  ++counters[PLUS];
  return self(base_iterator + n.base(false), generation, false);
}
@}

%% addition case 7 %%
%%%%%%%%%%%%%%%%%%%%%
@d \verb|iterator_counter operator+| , addition, case 7
@{friend self operator+(const UnadaptedDifference& n,
                      const self& i) {
  ++self::counters[PLUS];
  return self(n + i.base_iterator, i.generation, false);
}
@}

%% addition case 8 %%
%%%%%%%%%%%%%%%%%%%%%
@d \verb|difference_counter operator+| , addition, case 8
@{Iterator operator+ (const UnadaptedIterator& i) {
  ++counters[PLUS];
  return Iterator(i + base_difference);
}
@}

%% addition, case 9 %%
%%%%%%%%%%%%%%%%%%%%%%
@d \verb|iterator_counter operator+| , addition, case 9
@{friend self operator+ (const AdaptedDifference& n,
                       const self& i) {
  ++self::counters[PLUS];
  return self (i.base_iterator + n.base(false),
               i.generation, false);
}
@}


%% addition assign overview %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The addition assignment operation is broken into six cases:

\begin{tabular}{|l|l|l|l|l|}                                                           \hline
expr          & argument               & ret type    & counted in                &   \\ \hline
\verb|n += o| & Difference, Difference & Difference  & -                         &   \\
              & AdaptDiff, Difference  & AdaptDiff   & \verb|difference_counter| & 1 \\
              & Difference, AdaptDiff  & Difference  & \verb|difference_counter| & 2 \\
              & AdaptDiff, AdaptDiff   & AdaptDiff   & \verb|difference_counter| & 3 \\ \hline
\verb|i += n| & Iterator, Difference   & Iterator    & -                         &   \\
              & AdaptIter, Difference  & AdaptIter   & \verb|iterator_counter|   & 4 \\
              & Iterator, AdaptDiff    & Iterator    & \verb|difference_counter| & 5 \\
              & AdaptIter, AdaptDiff   & AdaptIter   & \verb|iterator_counter|   & 6 \\ \hline
\end{tabular}

\begin{tabular}{ll}
n, o  & object of class \verb|difference_type| \\
i     & object of class iterator               \\
\end{tabular}

%% addition assign case 1 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|difference_counter operator+=|, addition assign, case 1
@{self& operator+= (const UnadaptedDifference& y) {
  ++counters[PLUS_ASSIGN];
  base_difference += y;
  return *this;
}
@}

%% addition assign case 2 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|difference_counter operator+=|, addition assign, case 2
@{friend UnadaptedDifference& operator+= (UnadaptedDifference& x,
                                         const self& y) {
  ++counters[PLUS_ASSIGN];
  x += y.base_difference;
  return x;
}
@}

%% addition assign case 3 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|difference_counter operator+=|, addition assign, case 3
@{self& operator+= (const self& y) {
  ++counters[PLUS_ASSIGN];
  base_difference += y.base_difference;
  generation = max(generation, y.generation);
  return *this;
}
@}

%% addition assign case 4 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|iterator_counter operator+=|, addition assign, case 4
@{self& operator+= (const UnadaptedDifference& y) {
  ++counters[PLUS_ASSIGN];
  base_iterator += y;
  return *this;
}
@}

%% addition assign case 5 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|difference_counter operator+=|, addition assign, case 5
@{friend Iterator& operator+= (UnadaptedIterator& i,
                             const self& n) {
  ++counters[PLUS_ASSIGN];
  i += n.base_difference;
  return i;
}
@}

%% addition assign case 6 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|iterator_counter operator+=|, addition assign, case 6
@{self& operator+= (const AdaptedDifference& n) {
  ++counters[PLUS_ASSIGN];
  base_iterator += n.base(false);
  return *this;
}
@}

%% subtraction overview %%
%%%%%%%%%%%%%%%%%%%%%%%%%%
The subtraction operation is broken into nine cases:

\begin{tabular}{|l|l|l|l|l|}                                                           \hline
expr         & argument               & ret type    & counted in                &   \\ \hline
\verb|n - o| & Difference, Difference & Difference  & -                         &   \\
             & AdaptDiff, Difference  & AdaptDiff   & \verb|difference_counter| & 1 \\
             & Difference, AdaptDiff  & AdaptDiff   & \verb|difference_counter| & 2 \\
             & AdaptDiff, AdaptDiff   & AdaptDiff   & \verb|difference_counter| & 3 \\ \hline
\verb|i - n| & Iterator, Difference   & Iterator    & -                         &   \\
             & AdaptIter, Difference  & AdaptIter   & \verb|iterator_counter|   & 4 \\
             & Iterator, AdaptDiff    & Iterator    & \verb|difference_counter| & 5 \\
             & AdaptIter, AdaptDiff   & AdaptIter   & \verb|iterator_counter|   & 6 \\ \hline
\verb|i - j| & Iterator, Iterator     & Difference  & -                         &   \\
             & Iterator, AdaptIter    & AdaptDiff   & \verb|iterator_counter|   & 7 \\
             & AdaptIter, Iterator    & AdaptDiff   & \verb|iterator_counter|   & 8 \\
             & AdaptIter, AdaptIter   & AdaptDiff   & \verb|iterator_counter|   & 9 \\ \hline
\end{tabular}

\begin{tabular}{ll}
n, o  & object of class \verb|difference_type| \\
i, j  & object of class iterator               \\
\end{tabular}

%% subtraction case 1 %%
%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|difference_counter operator-| , subtraction, case 1
@{self operator- (const UnadaptedDifference& y) const {
  ++counters[MINUS];
  return self(base_difference - y, generation, false);
}
@}

%% subtraction case 2 %%
%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|difference_counter operator-| , subtraction, case 2
@{friend self operator- (const UnadaptedDifference& x,
                       const self& y) {
  ++counters[MINUS];
  return self(x - y.base_difference, y.generation, false);
}
@}

%% subtraction case 3 %%
%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|difference_counter operator-| , subtraction, case 3
@{self operator- (const self& y) const {
  ++counters[MINUS];
  return self(base_difference - y.base_difference,
              max(generation, y.generation), false);
}
@}

%% subtraction case 4 %%
%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|iterator_counter operator-| , subtraction, case 4
@{self operator- (const UnadaptedDifference& n) const {
  ++counters[MINUS];
  return self(base_iterator - n, generation, false);
}
@}

%% subtraction case 5 %%
%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|difference_counter operator-| , subtraction, case 5
@{friend Iterator operator- (const UnadaptedIterator& i,
                           const self& n) {
  ++counters[MINUS];
  return Iterator(i - n.base_difference);
}
@}

%% subtraction, case 6 %%
%%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|iterator_counter operator-| , subtraction, case 6
@{self operator- (const AdaptedDifference& n) const {
  ++counters[MINUS];
  return self(base_iterator - n.base(false), generation, false);
}
@}

%% subtraction case 7 %%
%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|iterator_counter operator-| , subtraction, case 7
@{friend AdaptedDifference operator- (const UnadaptedIterator& x,
                                    const self& y) {
  ++counters[MINUS];
  return AdaptedDifference(x - y.base_iterator, 1, false);
}
@}

%% subtraction case 8 %%
%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|iterator_counter operator-| , subtraction, case 8
@{AdaptedDifference operator- (const UnadaptedIterator& i) {
  ++counters[MINUS];
  return AdaptedDifference(base_iterator - i, 1, false);
}
@}

%% subtraction, case 9 %%
%%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|iterator_counter operator-| , subtraction, case 9
@{AdaptedDifference operator- (const self& i) {
  ++counters[MINUS];
  return AdaptedDifference (base_iterator -
                             i.base_iterator, 1, false);
}
@}

%% subtraction assign overview %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The subtraction assignment operation is broken into six cases:

\begin{tabular}{|l|l|l|l|l|}                                                           \hline
expr          & argument               & ret type    & counted in                &   \\ \hline
\verb|n -= o| & Difference, Difference & Difference  & -                         &   \\
              & AdaptDiff, Difference  & AdaptDiff   & \verb|difference_counter| & 1 \\
              & Difference, AdaptDiff  & Difference  & \verb|difference_counter| & 2 \\
              & AdaptDiff, AdaptDiff   & AdaptDiff   & \verb|difference_counter| & 3 \\ \hline
\verb|i -= n| & Iterator, Difference   & Iterator    & -                         &   \\
              & AdaptIter, Difference  & AdaptIter   & \verb|iterator_counter|   & 4 \\
              & Iterator, AdaptDiff    & Iterator    & \verb|difference_counter| & 5 \\
              & AdaptIter, AdaptDiff   & AdaptIter   & \verb|iterator_counter|   & 6 \\ \hline
\end{tabular}

\begin{tabular}{ll}
n, o  & object of class \verb|difference_type| \\
i     & object of class iterator               \\
\end{tabular}

%% subtraction assign case 1 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|difference_counter operator-=|, subtraction assign, case 1
@{self& operator-= (const UnadaptedDifference& y) {
  ++counters[MINUS_ASSIGN];
  base_difference -= y;
  return *this;
}
@}

%% subtraction assign case 2 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|difference_counter operator-=|, subtraction assign, case 2
@{friend UnadaptedDifference& operator-= (UnadaptedDifference& x,
                                         const self& y) {
  ++counters[MINUS_ASSIGN];
  x -= y.base_difference;
  return x;
}
@}

%% subtraction assign case 3 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|difference_counter operator-=|, subtraction assign, case 3
@{self& operator-= (const self& y) {
  ++counters[MINUS_ASSIGN];
  base_difference -= y.base_difference;
  generation = max(generation, y.generation);
  return *this;
}
@}

%% subtraction assign case 4 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|iterator_counter operator-=|, subtraction assign, case 4
@{self& operator-= (const UnadaptedDifference& y) {
  ++counters[MINUS_ASSIGN];
  base_iterator -= y;
  return *this;
}
@}

%% subtraction assign case 5 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|difference_counter operator-=|, subtraction assign, case 5
@{friend Iterator& operator-= (UnadaptedIterator& i,
                             const self& n) {
  ++counters[MINUS_ASSIGN];
  i -= n.base_difference;
  return i;
}
@}

%% subtraction assign case 6 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|iterator_counter operator-=|, subtraction assign, case 6
@{self& operator-= (const AdaptedDifference& n) {
  ++counters[MINUS_ASSIGN];
  base_iterator -= n.base(false);
  return *this;
}
@}

%% subscription overview %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%
The subscript operation is broken into three cases:

\begin{tabular}{|l|l|l|l|l|}                                                          \hline
expr        & argument               & ret type    & counted in                &   \\ \hline
\verb|i[n]| & Iterator, Difference   & Iterator    & -                         &   \\
            & AdaptIter, Difference  & AdaptIter   & \verb|iterator_counter|   & 1 \\
            & AdaptIter, AdaptDiff   & AdaptIter   & \verb|iterator_counter|   & 2 \\ \hline
\end{tabular}

\begin{tabular}{ll}
n, o  & object of class \verb|difference_type| \\
i     & object of class iterator               \\
\end{tabular}

%% subscription case 1 %%
%%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|iterator_counter operator[]|, subscripton, case 1
@{reference operator[] (const UnadaptedDifference& n) const {
  ++counters[SUBSCRIPT];
  return base_iterator[n];
}
@}

%% subscription case 2 %%
%%%%%%%%%%%%%%%%%%%%%%%%%
@d \verb|iterator_counter operator[]|, subscripton, case 2
@{reference operator[](const AdaptedDifference& n) const {
  ++counters[SUBSCRIPT];
  return base_iterator[n.base(false)];
}
@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Value Type Counting Adaptor}

@d \verb|value_counter| template parameter list 
@{template <class Value,
          COUNTERS_NAME_DECL_DEFAULT
          class Counter          = DEFAULT_COUNTER_TYPE>
@}

To simplify further declarations within this class, the type definition
\verb|self| is defined as follows:

@d \verb|value_counter| typedef self 
@{   typedef value_counter<Value, 
                         COUNTERS_NAME_PARM
                         Counter> self;
@}

%%  static variable definitions  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@d \verb|value_counter| counter variable definition 
@{template <class Value, 
          COUNTERS_NAME_DECL
          class Counter>
counter_vector<Counter>
value_counter<Value, 
              COUNTERS_NAME_PARM
              Counter>::
counters(COUNTERS_NAME_TEST ?
             "value_counter" : "", 
	 NCOUNTERS);
@}


%%  Overview of Operation  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%The STL concepts define which operation are required.  These required
%operations are shown in the following table. Some iterator adaptors
%have additional type requirements.

%\begin{tabular}{|l|l|l|}                                                      \hline
%                              & Expression        & Defined in Concept     \\ \hline
%Default constructor           & \verb|T()|        & Default Constructible  \\
%                              & \verb|T t;|       &                        \\ \hline
%Copy constructor              & \verb|T(t)|       & Assignable             \\
%                              & \verb|T t(s);|    &                        \\         
%                              & \verb|T t = s;|   &                        \\ \hline
%Assignment                    & \verb|t = s|      & Assignable             \\ \hline
%Swap                          & \verb|swap (t,s)| & Assignable             \\ \hline
%Equality                      & \verb|t == s|     & Equality Comparable    \\ \hline
%Inequality                    & \verb|t != s|     & Equality Comparable    \\ \hline
%Less                          & \verb|t < s|      & LessThan Comparable    \\ \hline
%Greater                       & \verb|t > s|      & LessThan Comparable    \\ \hline
%Less or equal                 & \verb|t <= s|     & LessThan Comparable    \\ \hline
%Greater or equal              & \verb|t >= s|     & LessThan Comparable    \\ \hline
%Pre-increment                 & \verb|++t|        &                        \\ \hline
%Post-increment                & \verb|t++|        &                        \\ \hline
%Pre-decrement                 & \verb|--t|        &                        \\ \hline
%Post-decrement                & \verb|t--|        &                        \\ \hline
%Left shift                    & \verb|t << i|     &                        \\ \hline
%Right shift                   & \verb|t >> i|     &                        \\ \hline
%Ostream                       & \verb|cout << t|  & ostream\_iterator      \\ \hline
%Istream                       & \verb|cin >> t|   & istream\_iterator      \\ \hline
%\end{tabular}

%\begin{tabular}{ll}
%T     & the class \verb|value|            \\
%t,s   & object of the class \verb|value|  \\
%i     & object of type \verb|int|         \\
%\end{tabular}

%%  default constructor  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%
The default constructor sets the generation to 1.

@d \verb|value_counter| default constructor 
@{value_counter () : //value_iterator(), 
                   generation(1) {
  ++counters[DEFAULT_CTOR];
}
@}

%%  copy constructor  %%
%%%%%%%%%%%%%%%%%%%%%%%%
The copy constructor takes the generation and increment it by one.  If this is
now the highest generation, it is set to the counter.

@d \verb|value_counter| copy constructor 
@{value_counter (const self& x)
     : base_value(x.base_value),
       generation(x.generation + 1) {
  ++counters[COPY_CTOR];
  counters[GENERATION] = max(counters[GENERATION], generation);
}
@}

@d \verb|value_counter| destructor 
@{~value_counter () { ++counters[DTOR]; }
@}

%%  external constructor  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In adddition to the default constructor and the copy constructor there
is a constructor which takes an object of the adapted iterator class
as an argument.  This is necessary for some iterator classes which
call special constructors.  For example, a back insert iterator takes
a container as an argument of its constructor. This external
constructor is called first and then the resulting object is given to
the counting adapter with this constructor.

@d \verb|value_counter| external constructor 
@{value_counter (const Value& v) : base_value(v),
                                 generation(1) {
  ++counters[OTHER_CTOR];
}
@}

The method \verb|base| gives the the base value back.
@d \verb|value_counter| base 
@{Value& base() {
  ++counters[BASE];
  return base_value;
}
@}

%%  uncounted constructor  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Some of the counting adaptor's member functions need to call a constructor.
In this case, this invocation of the constructor shoud not be counted.
However, the generation should be kept.  The following private
constructor is provided for this purpose.

@d \verb|value_counter| uncounted constructor 
@{value_counter (const self& x,
               const bool count)
  : base_value(x.base_value),
    generation(x.generation) {
  if (count)
    ++counters[COPY_CTOR];
}

value_counter (const Value& v,
               const Counter gen,
               const bool count) : base_value(v),
                                   generation(gen) {
  if (count)
    ++counters[OTHER_CTOR];
}
@}

%%  assignment %%
%%%%%%%%%%%%%%%%%
The assignment makes a copy. The generation isn't increased.
@d \verb|value_counter operator=| , assignment
@{self& operator=(const self& y) {
  ++counters[ASSIGNMENT];
  base_value = y.base_value;
  return *this;
}
@}

%% equality %%
%%%%%%%%%%%%%%
@d \verb|value_counter operator==|, equal
@{friend bool operator==(const self& x, const self& y) {
  ++self::counters[EQUALITY];
  return (x.base_value == y.base_value);
}
@}

%% less %%
%%%%%%%%%%
@d \verb|value_counter operator<| , less
@{friend bool operator<(const self& x, const self& y) {
  ++self::counters[LESS_THAN];
  return (x.base_value < y.base_value);
}
@}

@d \verb|value_counter operator++|, preincrement
@{self& operator++() {
  ++self::counters[PRE_INCREMENT];
  ++base_value;
  return *this;
}
@}

@d \verb|value_counter operator++|, postincrement
@{self operator++ (int) {
  self return_value (*this, false);
  ++counters[POST_INCREMENT];
  base_value++;
  return self(return_value, false);
}
@}

@d \verb|value_counter operator--|, predecrement
@{self& operator--() {
  ++self::counters[PRE_DECREMENT];
  --base_value;
  return *this;
}
@}

@d \verb|value_counter operator--|, postdecrement 
@{self operator-- (int) {
  self return_value (*this, false);
  ++counters[POST_DECREMENT];
  base_value--;
  return self(return_value, false);
}
@}

@d \verb|value_counter operator<<|, left shift 
@{self operator<< (int x) const {
  ++counters[LEFT_SHIFT];
  return self(base_value << x, false);
}
@}

@d \verb|value_counter operator<<=|, left shift assign 
@{self& operator<<= (int x) {
  ++counters[LEFT_SHIFT_ASSIGN];
  base_value <<= x;
  return *this;
}
@}

@d \verb|value_counter operator>>|, right shift 
@{self operator>> (int x) const {
  ++counters[RIGHT_SHIFT];
  return self(base_value >> x, false);
}
@}

@d \verb|value_counter operator>>=|, right shift assign 
@{self& operator>>= (int x) {
  ++counters[RIGHT_SHIFT_ASSIGN];
  base_value >>= x;
  return *this;
}
@}

@d \verb|value_counter operator+| , addition
@{friend self operator+ (const self& x, const self& y) {
  ++self::counters[PLUS];
  return self(x.base_value + y.base_value,
              max(x.generation, y.generation), false);
}
@}

@d \verb|value_counter operator+=|, addition assign
@{self& operator+= (const self& y) {
  ++counters[PLUS_ASSIGN];
  base_value += y.base_value;
  generation = max(generation, y.generation);
  return *this;
}
@}

@d \verb|value_counter operator-| , subtraction
@{friend self operator- (const self& x, const self& y) {
  ++self::counters[MINUS];
  return self(x.base_value - y.base_value,
              max(x.generation, y.generation), false);
}
@}

@d \verb|value_counter operator-=|, subtraction assign
@{self& operator-= (const self& y) {
  ++counters[MINUS_ASSIGN];
  base_value -= y.base_value;
  generation = max(generation, y.generation);
  return *this;
}
@}

@d \verb|value_counter operator*| , multiply
@{friend self operator* (const self& x, const self& y) {
  ++self::counters[TIMES];
  return self(x.base_value * y.base_value,
              max(x.generation, y.generation), false);
}
@}

@d \verb|value_counter operator*=|, multiply assign
@{self& operator*= (const self& y) {
  ++counters[TIMES_ASSIGN];
  base_value *= y.base_value;
  generation = max(generation, y.generation);
  return *this;
}
@}

@d \verb|value_counter operator/| , divide
@{friend self operator/ (const self& x, const self& y) {
  ++self::counters[DIVIDE];
  return self(x.base_value / y.base_value,
              max(x.generation, y.generation), false);
}
@}

@d \verb|value_counter operator/=|, divide assign
@{self& operator/= (const self& y) {
  ++counters[DIVIDE_ASSIGN];
  base_value /= y.base_value;
  generation = max(generation, y.generation);
  return *this;
}
@}


%% << %%
%%%%%%%%
@d \verb|value_counter operator<<|, ostream
@{friend ostream& operator<< (ostream& out, const self& t) {
  ++counters[OSTREAM];
  return out << t.base_value;
}
@}

%% >> %%
%%%%%%%%
@d \verb|value_counter operator>>|, istream
@{friend istream& operator>> (istream& i, self& t) {
  ++self::counters[ISTREAM];
  return i >> t.base_value;
}
@}


%%  put parts together  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%

@d \verb|value_counter| 
@{@<\verb|value_counter| template parameter list@>

class value_counter {

  @<\verb|value_counter| typedef self@>

  @<counter index enumeration@>
  @<declare and register counters@>

  Value base_value;
  @<declare generation@>

  @<\verb|value_counter| uncounted constructor@>

 public:
  @<\verb|value_counter| default constructor@>
  @<\verb|value_counter| copy constructor@>
  @<\verb|value_counter| destructor@>
  @<\verb|value_counter| external constructor@>
  @<\verb|value_counter| base@>

  @<\verb|value_counter operator=| , assignment@>
  @<\verb|value_counter operator==|, equal@>
  @<\verb|value_counter operator<| , less@>
  @<\verb|value_counter operator++|, preincrement@>
  @<\verb|value_counter operator++|, postincrement@>
  @<\verb|value_counter operator--|, predecrement@>
  @<\verb|value_counter operator--|, postdecrement@>
  @<\verb|value_counter operator<<|, left shift@>
  @<\verb|value_counter operator<<=|, left shift assign@>
  @<\verb|value_counter operator>>|, right shift@>
  @<\verb|value_counter operator>>=|, right shift assign@>
  @<\verb|value_counter operator+| , addition@>
  @<\verb|value_counter operator+=|, addition assign@>
  @<\verb|value_counter operator-| , subtraction@>
  @<\verb|value_counter operator-=|, subtraction assign@>
  @<\verb|value_counter operator*| , multiply@>
  @<\verb|value_counter operator*=|, multiply assign@>
  @<\verb|value_counter operator/| , divide@>
  @<\verb|value_counter operator/=|, divide assign@>
  @<\verb|value_counter operator<<|, ostream@>
  @<\verb|value_counter operator>>|, istream@>

};

@<\verb|value_counter| counter variable definition @>
@}

\subsection{Function Counting Adaptors}

\subsubsection{Generator Counting Adaptor}

The \verb|generator_counter| class is virtually identical to
% forced line-break due to overfull hbox
\\\verb|unary_function_counter|.  For details on the implementation the
reader should refer to the discussion of that class in section
\ref{sec:adaptor-reference}, page \pageref{sec:adaptor-reference}.

@d \verb|generator_counter| template parameter list 
@{template <class AdaptableGenerator, 
          COUNTERS_NAME_DECL_DEFAULT
          class Counter = DEFAULT_COUNTER_TYPE>
@}

@d \verb|generator_counter| counter variable definition 
@{template <class AdaptableGenerator, 
          COUNTERS_NAME_DECL
          class Counter>
counter_vector<Counter> 
generator_counter<AdaptableGenerator, 
                  COUNTERS_NAME_PARM
                  Counter>::
counters(COUNTERS_NAME_TEST ? 
             "generator_counter" : "", 
         NCOUNTERS);
@}

@d \verb|generator_counter| constructors 
@{generator_counter () : base_function(), generation(1) { 
  ++counters[DEFAULT_CTOR]; 
}
generator_counter (const AdaptableGenerator& x) 
  : base_function(x), generation(1) {
  ++counters[OTHER_CTOR]; 
}
@}

@d \verb|generator_counter| copy constructor 
@{generator_counter (const self& x)
  : base_function(x.base_function), generation(x.generation + 1) {
  ++counters[COPY_CTOR];
  counters[GENERATION] = max(counters[GENERATION], generation);
}
@}

@d \verb|generator_counter| counting operations 
@{self& operator= (const self& rhs) { 
  ++counters[ASSIGNMENT]; 
  base_function = rhs.base_function;
  return *this;
}
~generator_counter () { ++counters[DTOR]; }

result_type operator() () const {
  ++counters[FUNCTION_CALL];
  return base_function();
}
@}

@d \verb|generator_counter| 
@{@<\verb|generator_counter| template parameter list@>
class generator_counter {
  typedef typename AdaptableGenerator::result_type result_type;
  typedef generator_counter<AdaptableGenerator, Counter> self;

  @<counter index enumeration@>
  @<declare and register counters@>

  AdaptableGenerator base_function;
  @<declare generation@>

 public:
  @<\verb|generator_counter| constructors@>
  @<\verb|generator_counter| copy constructor@>
  @<\verb|generator_counter| counting operations@>
};

@<\verb|generator_counter| counter variable definition@>
@}

\subsubsection{Unary Function Counting Adaptor}

@d \verb|unary_function_counter| template parameter list 
@{template <class AdaptableUnaryFunction, 
          COUNTERS_NAME_DECL_DEFAULT
          class Counter = DEFAULT_COUNTER_TYPE>
@}

@d \verb|unary_function_counter| constructors 
@{unary_function_counter () : base_function(), generation(1) { 
  ++counters[DEFAULT_CTOR]; 
}
unary_function_counter (const AdaptableUnaryFunction& x) 
  : base_function(x), generation(1) {
  ++counters[OTHER_CTOR]; 
}
@}

@d \verb|unary_function_counter| copy constructor 
@{unary_function_counter (const self& x)
  : base_function(x.base_function), generation(x.generation + 1) {
  ++counters[COPY_CTOR];
  counters[GENERATION] = max(counters[GENERATION], generation);
}
@}

@d \verb|unary_function_counter| counting operations 
@{self& operator= (const self& rhs) { 
  ++counters[ASSIGNMENT]; 
  base_function = rhs.base_function;
  return *this;
}
~unary_function_counter () { ++counters[DTOR]; }

result_type operator() (const argument_type& arg) const {
  ++counters[FUNCTION_CALL];
  return base_function(arg);
}
@}

@d \verb|unary_function_counter| 
@{@<\verb|unary_function_counter| template parameter list@>
class unary_function_counter 
  : public unary_function<
        typename AdaptableUnaryFunction::argument_type,
        typename AdaptableUnaryFunction::result_type> {

  typedef unary_function_counter<AdaptableUnaryFunction, 
                                 Counter> self;

  @<counter index enumeration@>
  @<declare and register counters@>

  AdaptableUnaryFunction base_function;
  @<declare generation@>

 public:
  @<\verb|unary_function_counter| constructors@>
  @<\verb|unary_function_counter| copy constructor@>
  @<\verb|unary_function_counter| counting operations@>
};

@<\verb|unary_function_counter| counter variable definition@>
@}

\subsubsection{Binary Function Counting Adaptor}

The \verb|binary_function_counter| class is virtually identical to
% forced line-break due to overfull hbox
\\\verb|unary_function_counter|.  For details on the implementation of
counters in general, the reader should refer to the discussion in
section \ref{sec:adaptor-reference}, page \pageref{sec:adaptor-reference}.

@d \verb|binary_function_counter| template parameter list 
@{template <class AdaptableBinaryFunction, 
          COUNTERS_NAME_DECL_DEFAULT
          class Counter = DEFAULT_COUNTER_TYPE>
@}

@d \verb|binary_function_counter| counter variable definition 
@{template <class AdaptableBinaryFunction, 
          COUNTERS_NAME_DECL
          class Counter>
counter_vector<Counter> 
binary_function_counter<AdaptableBinaryFunction, 
                        COUNTERS_NAME_PARM
                        Counter>::
counters(COUNTERS_NAME_TEST ? 
             "binary_function_counter" : "", 
	 NCOUNTERS);
@}

@d \verb|binary_function_counter| constructors 
@{binary_function_counter () : base_function(), generation(1) { 
  ++counters[DEFAULT_CTOR]; 
}
binary_function_counter (const AdaptableBinaryFunction& x) 
  : base_function(x), generation(1) {
  ++counters[OTHER_CTOR]; 
}
@}

@d \verb|binary_function_counter| copy constructor 
@{binary_function_counter (const self& x)
  : base_function(x.base_function), generation(x.generation + 1) {
  ++counters[COPY_CTOR];
  counters[GENERATION] = max(counters[GENERATION], generation);
}
@}

@d \verb|binary_function_counter| counting operations 
@{self& operator= (const self& rhs) { 
  ++counters[ASSIGNMENT]; 
  base_function = rhs.base_function;
  return *this;
}
~binary_function_counter () { ++counters[DTOR]; }

result_type operator() (const first_argument_type& x,
                        const second_argument_type& y) const {
  ++counters[FUNCTION_CALL];
  return base_function(x, y);
}
@}

@d \verb|binary_function_counter| 
@{@<\verb|binary_function_counter| template parameter list@>
class binary_function_counter 
  : public binary_function<
        typename AdaptableBinaryFunction::first_argument_type,
        typename AdaptableBinaryFunction::second_argument_type,
        typename AdaptableBinaryFunction::result_type> {

  typedef binary_function_counter<AdaptableBinaryFunction, 
                                  Counter> self;

  @<counter index enumeration@>
  @<declare and register counters@>

  AdaptableBinaryFunction base_function;
  @<declare generation@>

 public:
  @<\verb|binary_function_counter| constructors@>
  @<\verb|binary_function_counter| copy constructor@>
  @<\verb|binary_function_counter| counting operations@>
};

@<\verb|binary_function_counter| counter variable definition@>
@}

\section{Summary}

@o counters.h -d 
@{#ifndef COUNTERS_H
#define COUNTERS_H

#include <iostream>
#include <iomanip>
#include <string>
#include <typeinfo>
#include <algorithm>
#include <functional>
#include <numeric>
#include <map>
#include <vector>

@<printable names bug definitions@>
@<default counter type@>

@<\verb|median_element| functor@>

@<\verb|counter_vector|@>
@<\verb|recorder|@>
@<\verb|difference_counter|@>
@<\verb|iterator_counter|@>
@<\verb|value_counter|@>
@<\verb|generator_counter|@>
@<\verb|unary_function_counter|@>
@<\verb|binary_function_counter|@>

#endif  // COUNTERS_H
@}

\section{Makefile}
@O Makefile -t 
@{# -*-Makefile-mode-*-
PROG=counters
TEST_SRC=test-cov.cc test-use.cc test-comp.cc test-inst.cc \
         test-corr.cc
SRC=Makefile @$(PROG).h @$(PROG).cc @$(PROG).tex @$(TEST_SRC)
    
CXXFLAGS=-g -Wall
CLEANUP = perl -i -ne 'print if (!/^\#line/ && (/\S/ .. !/\S/))'

# TEST_ROPE produces many warnings on gcc. 
# TEST_HASH is a problem when hash<T> is not defined
# TEST_INVALID_VOID produces warnings about void exprs
# TEST_TEMPORARY_BUFFER produces warnings about
#                       temporary_buffer<T>
ALL_TEST_COV_FLAGS = -DTEST_ROPE -DTEST_HASH -DTEST_INVALID_VOID \
                     -DTEST_TEMPORARY_BUFFER
TEST_COV_FLAGS=-DTEST_HASH -DTEST_ROPE

.PHONY: all test doc dvi ps preview pspreview clean nuweb

all: test doc nuweb doc

@$(PROG): @$(PROG).h @$(PROG).cc
	@$(CXX) @$(CXXFLAGS) @$(LDFLAGS) -o @$@@ @$@@.cc

src source: counters.h @$(TEST_SRC)
	@$(CLEANUP) counters.h @$(TEST_SRC)

test: test-cov test-use test-comp test-inst test-corr
test-cov: @$(PROG).h test-cov.cc
	@$(CXX) @$(CXXFLAGS) @$(TEST_COV_FLAGS) @$(LDFLAGS) \
	-o @$@@ @$@@.cc
test-use: @$(PROG).h test-use.cc
	@$(CXX) @$(CXXFLAGS) @$(LDFLAGS) -o @$@@ @$@@.cc
test-comp: @$(PROG).h test-use.cc
	@$(CXX) @$(CXXFLAGS) @$(LDFLAGS) \
	-DCOUNTERS_TEST_USE_TYPE='value_counter<int>' \
	-o @$@@ test-use.cc
test-inst: @$(PROG).h test-inst.cc
	@$(CXX) @$(CXXFLAGS) @$(LDFLAGS) -o @$@@ @$@@.cc
test-corr: @$(PROG).h test-corr.cc
	@$(CXX) @$(CXXFLAGS) @$(LDFLAGS) -o @$@@ @$@@.cc

doc: dvi
dvi: @$(PROG).dvi
@$(PROG).dvi: @$(PROG).tex
	latex @$(PROG).tex
	latex @$(PROG).tex
ps: @$(PROG).ps
@$(PROG).ps: @$(PROG).dvi
	dvips -o @$@@ @$(PROG).dvi
preview: dvi
	xdvi @$(PROG).dvi
pspreview: ps
	gv @$(PROG).ps

clean:
	@$(RM) core @$(PROG){.??*,.h,} *{~,.o} 

@$(SRC) nuweb: @$(PROG).w
	nuweb @$(PROG).w
@}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Test Plan and Results}

All testing was performed independently on three platforms: Red Hat
Linux 5.1 with \verb|egcs 2.90.29|, Solaris 2.6 with \verb|g++ 2.8.1|
and Debian Linux 2.1 with \verb|egcs-2.91.58|.  Results were
consistent on each platform and thus are not generally reported
separately.

\section{Usability}

In order to assess the usability of the library, the tsort2 program
for analysis of sort algorithms from \cite{musser:timing} was modified
to use the new library.  This proved to be a reasonably simple task.
The required changes are described below.

The original implementation included several files to define the
counting adaptors.  Those are all now defined in \verb|counters.h|.
This results in a short list of included headers.

@d usability test include files 
@{#include <assert.h>
#include <algo.h>
#include <vector.h>
#include <iostream.h>
#include <iomanip.h>
#include <fstream.h>
#include "counters.h"
@}

The original implementation had four rather complicated typedefs to
define the counting adaptor types.  The new version eliminates the
need to refer to the
% forced line-break due to overfull hbox
\\\verb|difference_counter| explicitly and also
simplifies the form of the other typedefs.  The user does not need to
specify as many redundant template parameters.

@d usability test typedefs 
@{#ifndef COUNTERS_TEST_USE_TYPE
#  define COUNTERS_TEST_USE_TYPE int
#endif

typedef COUNTERS_TEST_USE_TYPE U;
typedef value_counter<U> cdata;
typedef iterator_counter<vector<cdata >::iterator> citer;
@}

The type, \verb|U|, that is used to test the sorting is
conditionalized primarily in order to facilitate the composition test
(see \ref{sec:test:composition} on page
\pageref{sec:test:composition}).  Because of the way the vector is
initialized, the type must have a constructor taking an \verb|int|
argument and must be able to be compared to an \verb|int|.

The goal of the original implementation was to compare three sort
algorithms: Introsort \cite{musser:introsort}, Quicksort and heap
sort.  This was done using the STL sort algorithm as Quicksort.  Since
newer versions of STL have replaced that with Introsort, this was no
longer reasonable.  Thus, for the purposes of this test, the first two
algorithms are both Introsort.  This is not due to a limitation of
the operation counting software but simply to the fact that a good
Quicksort function was not available.

@d usability test algorithm definitions 
@{template <class Container>
void algorithm (int k, Container& x) {
  switch (k) {
//   case 0: introsort(citer(x.begin()), citer(x.end()));
  case 0: sort(citer(x.begin()), citer(x.end()));
     break;
  case 1: sort(citer(x.begin()), citer(x.end()));
     break;
  case 2: partial_sort(citer(x.begin()), citer(x.end()), 
                       citer(x.end()));
     break;
  }
}

const char* const headings[number_of_algorithms] = {
  "Introsort        ",
  "Introsort        ",
  "Heapsort         "
};
@}

The random number generator used in the original code was not
necessarily portable.  This was replaced by instantiation of the STL
subtractive random number generator.

@d usability test random number generator 
@{subtractive_rng random(S);
@}

The definition of the array of \verb|recorder|'s used to track the
statistics requires no template parameters compared with five in the
original program.

@d usability test recorder array 
@{recorder<> stats[number_of_algorithms];
@}

In a number of places the original code manipulated the operation
counts manually in order to adjust for setup operations that were not
part of the actual sort algorithms.  That code has been replaced with
the \verb|recorder|'s \verb|pause()|/\verb|resume()| idiom.

@d usability test randomize test vector 
@{stats[0].pause(); {
  random_shuffle(x.begin(), x.end(), random);
  y = x;
} stats[0].resume();
@}

@d usability test restore test vector 
@{stats[n].pause(); {
  x = y;
} stats[n].resume();
@}

@d usability test verify sorting 
@{stats[n].pause(); {
  for (int z = 0; z < N; ++z)
    assert(x[z] == U(z));
} stats[n].resume();
@}

Finally, the reporting code was changed to use the output operator
rather than the \verb|report()| method.  The final program is shown
below.  It is identical to the original except as described in the
preceding paragraphs.

@O test-use.cc -d 
@{/*

Example program for measuring the computing time of
algorithms.  This program both measures times and counts
operations; for a simpler example of only measuring times,
see tsort1.cpp

*/

/*
 * Copyright (c) 1997 Rensselaer Polytechnic Institute
 *
 * Permission to use, copy, modify, distribute and sell
 * this software and its documentation for any purpose is
 * hereby granted without fee, provided that the above
 * copyright notice appear in all copies and that both that
 * copyright notice and this permission notice appear in
 * supporting documentation.  Rensselaer Polytechnic
 * Institute makes no representations about the suitability
 * of this software for any purpose.  It is provided "as
 * is" without express or implied warranty.
 */

@<usability test include files@>
@<usability test typedefs@>

const int number_of_algorithms = 3;
const int number_of_trials = 7;

@<usability test algorithm definitions@>

int main () {
  int N0, N1, N2, N, S;

  const int factor = 1000;

  cout << "All sequence sizes are in multiples of "
       << factor << ".\n";
  cout << "Input the smallest and largest sequence sizes: "
       << flush;
  cin >> N1 >> N2;

  cout << "Input random seed control (a positive integer): ";
  cin >> S;

  @<usability test random number generator@>

  ofstream ofs1("read.dat");
  ofstream ofs2("graph.dat");

  @<usability test recorder array@>

  vector<cdata> x, y;
  x.reserve(N2 * factor);
  y.reserve(N2 * factor);

  int repetitions = max(32 / N1, 1);
  int n;

  cout << endl;
  ofs1 << endl;

  for (N0 = N1; N0 <= N2; N0 *= 2) {
    N = N0 * factor;

    cout << "Size: " << setw(4) << N0 << "   Trials: " << flush;
    ofs1  << "Size: " << setw(4) << N0 << endl << flush;
    ofs2  << setw(4) << N0 << "\t" << flush;

    for (int i = 0; i < N; ++i)
      x.push_back(U(i));

    int p, q;
    for (p = 0; p < number_of_trials; ++p) {
      @<usability test randomize test vector@>

      cout << (p + 1) << ":" << flush;

      for (n = 0; n < number_of_algorithms; ++n) {
        for (q = 0; q < repetitions; ++q) {
          @<usability test restore test vector@>
          algorithm(n, x);
        }

        @<usability test verify sorting@>

        cout << (n + 1) << flush;
        stats[n].record();
      }
      cout << ", " << flush;
    }

    for (n = 0; n < number_of_algorithms; ++n) {
      cout << headings[n] << endl;
      stats[n].report_headings(cout);
      stats[n].report_table(cout, 
          &median_element<counter_vector<>::const_iterator>);
      stats[n].report_totals(cout, 
          &median_element<counter_vector<>::const_iterator>);

      ofs1 << headings[n] << endl;
      stats[n].report_headings(ofs1);
      stats[n].report_table(ofs1, 
          &median_element<counter_vector<>::const_iterator>);
      stats[n].report_totals(ofs1, 
          &median_element<counter_vector<>::const_iterator>);

      stats[n].report_totals(ofs2, 
          &median_element<counter_vector<>::const_iterator>);
    }

    cout << endl;
    ofs1 << endl;
    ofs2 << endl;

    x.erase(x.begin(), x.end());

    if (repetitions > 1)
      repetitions /= 2;
  }
  return 0;
}
@}

This test is by nature a very subjective ``test.''  Its success or
failure is defined by whether the new library is ``easier to use''
than the original.  Although this judgement is a matter of opinion,
there are a number of factual observations that can be made.

The new source code has 12 percent fewer lines and 22 percent fewer
characters (since many code lines were simplified).  Additionally the
simple fact that most of the program remained unchanged is an
indicator that using the new library does not require a large amount
of user effort.

\section{Coverage}

One of the constraints on the library is that the counting adaptors
must implement a sufficient set of operations to be useful within the
context of STL.  For example, the STL \verb|inner_product()| function
requires a type that supports addition and multiplication.  Thus, it
is important that the \verb|value_counter| provide counting versions
of those operations.

One way to verify this is to write a program that instantiates each
STL data structure and calls each STL algorithm at least once using
counting adaptors whenever possible.  This was done by defining a
variety of template functions that make it easy to create the
structures and invoke the algorithms on a variety of data types.

It should be emphasized that the goal of this test is merely to force
the compiler to reference each data structure and algorithm.
Semantically the invocations may not make sense.  In fact, it is most
likely that if this program were executed it would either abort or
would not terminate at all.  This test succeeds simply when the
program compiles cleanly.

To create and test the container types, two functions are used.  The
first creates one of each of the basic STL containers.  The second
function takes a particular container type and performs the relevant
tests --- in this case creating counting versions of each of
the container's iterator types.

@d coverage test of containers 
@{template <class T>
void instantiate_containers () {
  instantiate_container(vector<T>());
  instantiate_container(deque<T>());
  instantiate_container(list<T>());
  instantiate_container(slist<T>());
  instantiate_container(bit_vector());
  instantiate_container(set<T>());
  instantiate_container(map<T, T>());
  instantiate_container(multiset<T>());
  instantiate_container(multimap<T, T>());
#ifdef TEST_HASH
  instantiate_container(hash_set<T>());
  instantiate_container(hash_map<T, T>());
  instantiate_container(hash_multiset<T>());
  instantiate_container(hash_multimap<T, T>());
#endif
  instantiate_container(basic_string<char>());
#ifdef TEST_ROPE
  instantiate_container(rope<char>());
#endif
}
@}

@d coverage test of a single container 
@{template <class Container>
void instantiate_container (const Container&) {
  volatile iterator_counter<typename Container::iterator> i;
  (void)i;
  volatile iterator_counter<typename Container::const_iterator> ci;
  (void)ci;
}  
@}

Note the use of \verb|volatile| here and elsewhere to ensure that the
compiler does not optimize the unused variables out of the program.

Next the program tests the iterator manipulation functions,
\verb|distance()| and
% forced line-break due to overfull hbox
\\\verb|advance()|.  This is done by three
functions.  Since the iterator functions may be implemented
differently for each of the STL iterator concepts, it is important to
use each of those five concepts.  The first test function does this.
The second and third functions take a particular container or iterator
type and invoke the iterator functions for that type.

@d coverage test of iterator functions 
@{template <class T>
void instantiate_iterator_functions () {
  instantiate_iterator_functions(istream_iterator<T>(cin),
				 istream_iterator<T>());  // input
#ifdef TEST_HASH
  instantiate_iterator_functions(hash_set<T>());  // forward
#endif
  instantiate_iterator_functions(list<T>());  // reversible
  instantiate_iterator_functions(vector<T>());  // random access
}
@}

@d coverage test of iterator functions on a container 
@{template <class Container>
void instantiate_iterator_functions (Container x) {
  instantiate_iterator_functions(x.begin(), x.end());
}
@}

@d coverage test of iterator functions on a given iterator 
@{template <class InputIterator>
void instantiate_iterator_functions (const InputIterator& begin,
				     const InputIterator& end) {
  iterator_counter<InputIterator> cbegin(begin), cend(end);
  distance(cbegin, cend);
  advance(cbegin, 1);
}
@}

Next the built-in iterator adaptor types are tested.  Most of these
are parameterized on the \verb|value_type| of the iterator.  In cases
where the template parameter is a container or another iterator type,
\verb|list| is chosen arbitrarily as the base type.

@d coverage test of iterator adaptors 
@{template <class T>
void instantiate_iterators () {
  typedef list<T> Container;
  typedef iterator_counter<Container::iterator> Iterator;
  Container x;
  volatile iterator_counter<istream_iterator<T> > i1(cin);
  (void)i1;
  volatile iterator_counter<ostream_iterator<T> > i2(cout);
  (void)i2;
  volatile iterator_counter<front_insert_iterator<Container> > 
      i3(front_insert_iterator<Container>(x)); (void)i3;
  volatile iterator_counter<back_insert_iterator<Container> > 
      i4(back_insert_iterator<Container>(x)); (void)i4;
  volatile iterator_counter<insert_iterator<Container> > 
      i5(insert_iterator<Container>(x, x.begin())); (void)i5;
  volatile iterator_counter<reverse_iterator<Iterator> > 
      i6(reverse_iterator<Iterator>()); (void)i6;
  volatile iterator_counter<raw_storage_iterator<Iterator, T> > 
      i7(raw_storage_iterator<Iterator, T>(x.begin())); (void)i7;
#ifdef TEST_ROPE
  volatile iterator_counter<sequence_buffer<Container> > 
      i8(sequence_buffer<Container>(x)); (void)i8;
#endif
}
@}

The largest portion of this test is algorithm instantiation.  Like the
iterator manipulation functions, some of the algorithms may have
different implementations for different iterator concepts.  Indeed
some of the algorithms are restricted to only a subset of the iterator
concepts.  For this reason, as is explained in more detail below, the
\verb|iterator_traits| mechanism is used to determine an iterator's
category.

The first function instantiates the algorithms for one of each
iterator concept.  In addition, there are several algorithms that are
defined only for numeric types.  These are treated separately in
% forced line-break due to overfull hbox
\\\verb|instantiate_numeric_algorithms()|.

@d coverage test of algorithms 
@{template <class T>
void instantiate_algorithms () {
  instantiate_algorithms(istream_iterator<T>(cin),
			 istream_iterator<T>());  // input
#ifdef TEST_HASH
  instantiate_algorithms(hash_set<T>());  // forward
#endif
  instantiate_algorithms(list<T>());  // reversible
  instantiate_algorithms(vector<T>());  // random access
  instantiate_numeric_algorithms();
}
@}

@d coverage test of numeric algorithms 
@{void instantiate_numeric_algorithms () {
  typedef value_counter<int> value_type;
  vector<value_type> x;
  iterator_counter<vector<value_type>::iterator> begin(x.begin()), 
                                                 end(x.end());
  ostream_iterator<value_type> out(cout);

  iota(begin, end, value_type());
  accumulate(begin, end, value_type(0));
  accumulate(begin, end, value_type(0), plus<value_type>());
  inner_product(begin, end, begin, value_type(0));
  inner_product(begin, end, begin, value_type(0),
		plus<value_type>(), multiplies<value_type>());
  partial_sum(begin, end, out);
  partial_sum(begin, end, out, plus<value_type>());
  adjacent_difference(begin, end, out);
  adjacent_difference(begin, end, out, minus<value_type>());
#if 0
  power(value_type(2), value_type(2));
  power(value_type(2), value_type(2), multiplies<value_type>());
#endif
}
@}

The algorithm instantiation functions parameterized on
\verb|Container| and
% forced line-break due to overfull hbox
\\\verb|Iterator| types simply compute the
iterator's category and invoke the appropriate sub-function.

@d coverage test of algorithms on a container 
@{template <class Container>
void instantiate_algorithms (Container x) {
  instantiate_algorithms(x.begin(), x.end());
}
@}

@d coverage test of algorithms on a given iterator 
@{template <class Iterator>
void instantiate_algorithms (const Iterator& begin, 
                             const Iterator& end) {
  iterator_counter<Iterator> cbegin(begin), cend(end);
  instantiate_algorithms(cbegin, cend, 
			 iterator_traits<Iterator>::
	                 iterator_category());
}
@}

The is a specialized algorithm instantiation function for each
iterator category.  Since 
% forced line-break due to overfull hbox
\\\verb|Random Access Iterator|s are also
\verb|Bidirectional Iterators| the random access iterator function
also calls the bidirectional iterator function.  Similarly the
bidirectional iterator function calls the forward iterator function
and so on, chaining down to the level of input iterators.  Each
function invokes only those functions that are specifically defined
for that particular iterator category.

@d coverage test of algorithms on random access iterators 
@{template <class Iterator>
void instantiate_algorithms (Iterator& begin, Iterator& end, 
			     random_access_iterator_tag) {
  typedef typename Iterator::value_type value_type;
  typedef equal_to<value_type> predicate_type;
  predicate_type f;
  binary_function_counter<predicate_type> bp(f);
  unary_function_counter<binder2nd<predicate_type> > 
    up(bind2nd(f, value_type()));

#ifdef TEST_INVALID_VOID
  random_shuffle(begin, end); // random
  random_sample(begin, end, begin, end); // 1st pair fwd, 
                                         // 2nd pair random
#endif
  sort(begin, end); // random
  sort(begin, end, bp); // random
  stable_sort(begin, end); // random
  stable_sort(begin, end, bp); // random
  partial_sort(begin, end, end); // random
  partial_sort(begin, end, end, bp); // random
  partial_sort_copy(begin, end, begin, end); // 1st pair input,
                                            // 2nd pair random
  partial_sort_copy(begin, end, begin, end, bp); //   "    " 
  nth_element(begin, end, end); // random
  nth_element(begin, end, end, bp); // random
  push_heap(begin, end); // random
  push_heap(begin, end, bp); // random
  pop_heap(begin, end); // random
  pop_heap(begin, end, bp); // random
#ifdef TEST_INVALID_VOID
  make_heap(begin, end); // random
  make_heap(begin, end, bp); // random
#endif
  sort_heap(begin, end); // random
  sort_heap(begin, end, bp); // random
  is_heap(begin, end); // random
  is_heap(begin, end, bp); // random

  instantiate_algorithms(begin, end, bidirectional_iterator_tag());
}
@}

@d coverage test of algorithms on bidirectional iterators 
@{template <class Iterator>
void instantiate_algorithms (Iterator& begin, Iterator& end, 
			     bidirectional_iterator_tag) {
  typedef typename Iterator::value_type value_type;
  typedef equal_to<value_type> predicate_type;
  predicate_type f;
  binary_function_counter<predicate_type> bp(f);
  unary_function_counter<binder2nd<predicate_type> > 
    up(bind2nd(f, value_type()));
  ostream_iterator<value_type> out(cout);

  copy_backward(begin, end, end); // bidir
  reverse(begin, end); // bidir
  reverse_copy(begin, end, out); // bidir
#ifdef TEST_TEMPORARY_BUFFER
  inplace_merge(begin, end, end); // bidir
  inplace_merge(begin, end, end, bp); // bidir
#endif
  next_permutation(begin, end); // bidir
  next_permutation(begin, end, bp); // bidir
  prev_permutation(begin, end); // bidir
  prev_permutation(begin, end, bp); // bidir

  instantiate_algorithms(begin, end, forward_iterator_tag());
}
@}

@D coverage test of algorithms on forward iterators 
@{template <class Iterator>
void instantiate_algorithms (Iterator& begin, Iterator& end, 
			     forward_iterator_tag) {
  typedef typename Iterator::value_type value_type;
  typedef equal_to<value_type> predicate_type;
  predicate_type f;
  binary_function_counter<predicate_type> bp(f);
  unary_function_counter<binder2nd<predicate_type> > 
    up(bind2nd(f, value_type()));
  ostream_iterator<value_type> out(cout);

  adjacent_find(begin, end); // fwd
  adjacent_find(begin, end, bp); // fwd
  find_first_of(begin, end, begin, end); // 2nd pair fwd
  find_first_of(begin, end, begin, end, bp); // 2nd pair fwd
  search(begin, end, begin, end); // fwd
  search(begin, end, begin, end, bp); // fwd
  search_n(begin, end, 1, value_type()); // fwd
  search_n(begin, end, 1, value_type(), bp); // fwd
  find_end(begin, end, begin, end); // fwd
  find_end(begin, end, begin, end, bp); // fwd
  copy_backward(begin, end, end); // bidir
  iter_swap(begin, end);
  swap_ranges(begin, end, begin); // fwd
  replace(begin, end, value_type(), value_type()); // fwd
  replace_if(begin, end, up, value_type()); // fwd
  fill(begin, end, value_type()); // fwd
  fill_n(out, 1, value_type());
//   generate(begin, end, /* generator */); // fwd 
  remove(begin, end, value_type()); // fwd
  remove_if(begin, end, up); // fwd
  unique(begin, end); // fwd
  unique(begin, end, bp); // fwd
  rotate(begin, end, end); // fwd
  rotate_copy(begin, end, end, out); // fwd
  random_sample_n(begin, end, out, 1); // fwd
  partition(begin, end, up); // fwd
#ifdef TEST_TEMPORARY_BUFFER
  stable_partition(begin, end, up); // fwd
#endif
  is_sorted(begin, end); // fwd
  is_sorted(begin, end, bp); // fwd
  lower_bound(begin, end, value_type()); // fwd
  lower_bound(begin, end, value_type(), bp); // fwd
  upper_bound(begin, end, value_type()); // fwd
  upper_bound(begin, end, value_type(), bp); // fwd
  equal_range(begin, end, value_type()); // fwd
  equal_range(begin, end, value_type(), bp); // fwd
  binary_search(begin, end, value_type()); // fwd
  binary_search(begin, end, value_type(), bp); // fwd
  min_element(begin, end);
  min_element(begin, end, bp);
  max_element(begin, end);
  max_element(begin, end, bp);

  instantiate_algorithms(begin, end, input_iterator_tag());
}
@}

@D coverage test of algorithms on input iterators 
@{template <class Iterator>
void instantiate_algorithms (Iterator& begin, Iterator& end, 
			     input_iterator_tag) {
  typedef typename Iterator::value_type value_type;
  typedef equal_to<value_type> predicate_type;
  predicate_type f;
  binary_function_counter<predicate_type> bp(f);
  unary_function_counter<binder2nd<predicate_type> > 
      up(bind2nd(f, value_type()));
  ostream_iterator<value_type> out(cout);

  for_each(begin, end, up);
  find(begin, end, value_type());
  find_if(begin, end, up);
  count(begin, end, value_type());
  count_if(begin, end, up);
  mismatch(begin, end, begin);
  mismatch(begin, end, begin, bp);
  equal(begin, end, begin);
  equal(begin, end, begin, bp);
  copy(begin, end, out);
  copy_n(begin, 1, out);
  swap(begin, end);
  transform(begin, end, out, identity<value_type>());
  transform(begin, end, begin, out, 
            project1st<value_type, value_type>());
  replace_copy(begin, end, out, value_type(), value_type());
  replace_copy_if(begin, end, out, up, value_type());
//   generate_n(out, 1, /* generator */); // 
  remove_copy(begin, end, out, value_type());
  remove_copy_if(begin, end, out, up);
  unique_copy(begin, end, out);
  unique_copy(begin, end, out, bp);
  merge(begin, end, begin, end, out);
  merge(begin, end, begin, end, out, bp);
  includes(begin, end, begin, end);
  includes(begin, end, begin, end, bp);
  set_union(begin, end, begin, end, out);
  set_union(begin, end, begin, end, out, bp);
  set_intersection(begin, end, begin, end, out);
  set_intersection(begin, end, begin, end, out, bp);
  set_difference(begin, end, begin, end, out);
  set_difference(begin, end, begin, end, out, bp);
  set_symmetric_difference(begin, end, begin, end, out);
  set_symmetric_difference(begin, end, begin, end, out, bp);
  min(value_type(), value_type());
  min(value_type(), value_type(), bp);
  max(value_type(), value_type());
  max(value_type(), value_type(), bp);
  lexicographical_compare(begin, end, begin, end);
  lexicographical_compare(begin, end, begin, end, bp);
  lexicographical_compare_3way(begin, end, begin, end);
}
@}

The last form of STL class is the function object.  The function below
instantiates each of these on an arbitrary type.  Certain functions
are defined only for numeric types.  Those are instantiated on an
operation counting \verb|int|, regardless of the type parameter of the
function.

@d coverage test of function objects 
@{template <class T>
void instantiate_functions () {
  plus<value_counter<int> >();
  minus<value_counter<int> >();
  multiplies<value_counter<int> >();
  divides<value_counter<int> >();
  modulus<value_counter<int> >();
  negate<value_counter<int> >();
  equal_to<T>();
  not_equal_to<T>();
  less<T>();
  greater<T>();
  less_equal<T>();
  greater_equal<T>();
  logical_and<value_counter<int> >();
  logical_or<value_counter<int> >();
  logical_not<value_counter<int> >();
  identity<T>();
  project1st<T, T>();
  project2nd<T, T>();
  select1st<pair<T, T> >();
  select2nd<pair<T, T> >();
}
@}

Finally the test program is completed by a function that applies each
of the individual instantiation functions to an arbitrary type.  The
\verb|main()| function then calls this function on a wide variety of
fundamental and container types, in both their counting and
non-counting forms.

@d coverage test on type T 
@{template <class T>
void instantiate () {
  instantiate_containers<T>();
  instantiate_iterator_functions<T>();
  instantiate_iterators<T>();
#ifdef TEST_INVALID_VOID
  instantiate_algorithms<T>();
#endif
  instantiate_functions<T>();
}
@}

@o test-cov.cc -d 
@{#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <slist>
#include <bvector.h>
#include <set>
#include <map>
#ifdef TEST_HASH
#include <hash_set>
#include <hash_map>
#endif
#ifdef TEST_ROPE
#include <rope>
#endif
#include <stack>
#include <queue>
#include <iterator>
#include <algorithm>
#include <functional>

#include "counters.h"

@<coverage test of a single container@>
@<coverage test of containers@>
@<coverage test of iterator functions on a given iterator@>
@<coverage test of iterator functions on a container@>
@<coverage test of iterator functions@>
@<coverage test of iterator adaptors@>
@<coverage test of algorithms on input iterators@>
@<coverage test of algorithms on forward iterators@>
@<coverage test of algorithms on bidirectional iterators@>
@<coverage test of algorithms on random access iterators@>
@<coverage test of algorithms on a given iterator@>
@<coverage test of algorithms on a container@>
@<coverage test of numeric algorithms@>
@<coverage test of algorithms@>
@<coverage test of function objects@>

@<coverage test on type T@>

int main () {
  instantiate<int>();
}
@}

One will notice that a number of portions of this test are
conditionalized.  In practice it is difficult to instantiate all of
the STL algorithms, even when the adaptors are implemented correctly.
The problems are discussed below.

The hash-based containers in STL require that \verb|hash<T>| be
defined for the container's \verb|value_type|.  This means that each
instantiated type must have a specialized definition for
\verb|hash<T>|.  Furthermore, the hash include file produces warnings
from the compiler independent from the counting adaptor library.  For
this reason, all hash-related code is conditionalized (it is included
by default), and the functions are instantiated only for the
\verb|int| type.

The \verb|rope| include file also produces warnings from the compiler.
Thus, the \verb|rope| code is also conditionalized (but included by
default).  The test succeeds --- the program compiles --- when the
hash and rope code is included, but it does not proceed free of
warnings.

Instantiating many of the algorithms produces an inexplicable error
message about a void expression.  Isolating the problematic code into
a smaller test case does not reproduce the message.  Thus, all of the
algorithms can be instantiated on an individual basis, just not all at
once in a single program.  This would appear to be a compiler
limitation.  For this reason, those troublesome functions are
conditionalized temporarily until the compiler is more able to handle
large, nested template invocations.

There is one legitimate omission that was uncovered with this test.
\verb|stable_sort()| and \verb|inplace_merge()| use the
\verb|temporary_buffer| type.  Instantiating this type with counting
adaptors produces an error which has not yet been resolved.  For this
reason, those algorithms are not included in the test.

Finally, even with all of these problems controlled by conditional
compilation, when more than one type is instantiated in the
\verb|main()| function, the compiler frequently runs out of memory.
With all of the template instantiations involved, the processing
required to produce an executable is simply too much for the compiler.

With all these caveats, it does appear that the library is successful
in covering the required operations.  The massive complexity of this
test presents compilation problems, but they do not appear to be due
to the library itself.  When the test's size is controlled carefully,
it succeeds.  Rephrased, the problems appear to be related to the
ambitiousness of the test itself rather than to defficiencies in the
library.

\section{Instantiation}

Because member functions of template classes are not instantiated
unless they are invoked, it is possible for a program to contain
undetected errors unless each function is referenced.  This forces the
compiler to process the function, checking it for syntax errors.  The
program below does this for each of the counting adaptor types.  Like
the coverage test, this test succeeds if the program compiles
successfully.  It is not necessarily appropriate to execute the
resulting program.

@O test-inst.cc -d 
@{#include <vector>
#include "counters.h"

//    istream& operator>> (istream& i, int v) {
//cout << "int >>" << endl;
//      return i;
//}

class myGenerator {

   typedef int result_type;

public:

   myGenerator () {}

   myGenerator (const myGenerator& g) {}

   int operator() () const {
       return 1;
   }
};

int main()

{
  typedef vector<int> int_vector;
  typedef int_vector::iterator        vector_iterator;
  typedef int_vector::difference_type vector_difference;

  typedef iterator_counter<vector_iterator>
             counted_vector_iterator;

  typedef difference_counter<vector_difference, vector_iterator>
             counted_vector_difference;

  typedef value_counter<int> counted_int;

  typedef generator_counter<myGenerator> int_gen;

  recorder<> r;

  int_vector v;

  for (int i = 0; i < 5; i++) {
    v.push_back (i+100);
  };

  bool b;
  int i;
  int d;
  vector_iterator unadIter;

  // iterator_counter //
  //////////////////////

  // default constructor
  counted_vector_iterator def_const_iter;

  // external constructor
  counted_vector_iterator iter1(v.begin());

  // base
  unadIter = iter1.base();

  // copy constructor
  counted_vector_iterator iter2 = iter1;

  // Assignment
  iter1 = iter2;

  // Equality
  b = (iter1 == iter2);

  // Less
  b = (iter1 < iter2);

  // dereference
  i = *iter1;

  //preincrement
  ++iter1;

  //postincrement
  iter1++;

  //predecrement
  --iter1;

  //postdecrement
  iter1--;


  // difference_counter //
  ////////////////////////

  // default constructor
  counted_vector_difference def_const_diff;

  // external constructor
  counted_vector_difference diff1(v.end()-v.begin());

  // copy constructor
  counted_vector_difference diff2 = diff1;

  vector_difference unaptdiff = diff1.base();
  (void)unaptdiff; // use the variable

  // Assignment
  diff1 = diff2;

  // Equality
  b = (diff1 == diff2);

  // Less
  b = (diff1 < diff2);

  //preincrement
  ++diff1;

  //postincrement
  diff1++;

  //predecrement
  --diff1;

  //postdecrement
  diff1--;

  //multiply
  diff2 = diff1 * 5;
  diff2 = 5     * diff1;
  diff2 = diff1 * diff1;

  //multiply assign
  diff2 *= 5;
  d     *= diff1;
  diff2 *= diff1;

  //divide
  diff2 = diff1 / 5;
  diff2 = 5     / diff1;
  diff2 = diff1 / diff1;

  //divide assign
  diff2 /= 5;
  d     /= diff1;
  diff2 /= diff1;

  // ostream
  cout << diff1 << endl;


  // mixed operation //
  /////////////////////

  //addition
  diff2    = diff1     + 5;
  diff2    = 5         + diff1;
  diff2    = diff1     + diff1;

  iter2    = iter1     + 5;  
  unadIter = v.begin() + diff1;
  iter2    = iter1     + diff1;

  iter2    = 5         + iter1;  
  unadIter = diff1     + v.begin();
  iter2    = diff1     + iter1;
 

  //addition assign
  diff2    += 5;
  d        += diff1;
  diff2    += diff1;

  iter2    += 5;  
  unadIter += diff1;
  iter2    += diff1;

  //subtraction
  diff2    = diff1     - 5;
  diff2    = 5         - diff1;
  diff2    = diff1     - diff1;

  iter2    = iter1     - 5;  
  unadIter = v.begin() - diff1;
  iter2    = iter1     - diff1;

  diff1    = v.begin() - iter2;  
  diff1    = iter1     - v.begin();
  diff1    = iter1     - iter2;

  //subtraction assign
  diff2    -= 5;
  d        -= diff1;
  diff2    -= diff1;

  iter2    -= 5;  
  unadIter -= diff1;
  iter2    -= diff1;


  i = iter1[5];  
  i = iter1[diff1];

  // value_counter //
  ///////////////////

  // default constructor
  counted_int default_int;

  // external constructor
  counted_int val1(1234);

  // copy constructor
  counted_int val2 = val1;

  // Assignment
  val1 = val2;

  // base
  int unadval = val1.base();
  (void)unadval; // use the variable

  // Equality
  b = (val1 == val2);

  // Less
  b = (val1 < val2);

  //preincrement
  ++val1;

  //postincrement
  val1++;

  //predecrement
  --val1;

  //postdecrement
  val1--;

  //multiply
  val2 = val1 * val1;

  //multiply assign
  val2 *= val1;

  //divide
  val2 = val1 / val1;

  //divide assign
  val2 /= val1;

  //addition
  val2    = val1     + val1;

  //addition assign
  val2    += val1;

  //subtraction
  val2    = val1     - val1;

  //subtraction assign
  val2    -= val1;

  // ostream
  cout << val1 << endl;

  // istream
  if (false)
     cin >> val2;

  // generator_counter //
  ///////////////////////
  myGenerator unad_gen;

  // default constructor
  int_gen     def_gen;

  // external constructor
  int_gen     gen1(unad_gen);

  // copy constructor
  int_gen     gen2(gen1);

  // operator ()
  int_gen::result_type res = gen1();  
  (void)res; // use the variable

  r.record();
  cout << r;
}

void tst_iter () {
  @<\verb|iterator_counter| example of use@>
}
void tst_diff () {
  @<\verb|difference_counter| example of use@>
}
void tst_gen () {
  @<\verb|generator_counter| example of use@>
}
void tst_una () {
  @<\verb|unary_function_counter| example of use@>
}
void tst_bin () {
  @<\verb|binary_function_counter| example of use@>
}
void tst_val () {
  @<\verb|value_counter| example of use@>
  (void)b; // use the variable
}
@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Composition}

\label{sec:test:composition}
It is important that if operation \verb|X| is invoked on a counting
adaptor, the adaptor must in turn invoke operation \verb|X|, and not
some other operation \verb|Y|, on its base type.  One convenient way
to test this is to compose a counting adaptor with another.  In other
words, rather than using a \verb|value_counter<int>|, use
% forced line-break due to overfull hbox
\\\verb|value_counter<value_counter<int> >|.  Then the operation counts
produced by the outer counter must equal those from the inner counter.

In practice it is not easy to obtain independent results for the inner
and outer counters.  However, there is another way to obtain the same
result.  First the test is run on a non-nested counting type, such as
\verb|value_counter<int>|.  These results are used as a baseline
case.

Then when the program is run with composed adaptors, each operation on
the outer type will result in two operations being counted.  First the
outer type will count the operation and defer to its base type, the
inner counter.  Then the inner counter will count the operation and
defer to its base type.  Thus, the results from the composed adaptors
should show exactly double the counts as are in the baseline case.

This test was performed by reusing the code from the usability test.
First the program was run using adapted integers as the type to be
sorted.  Then it was rerun using composed adaptors.  The resulting
operation counts were in fact doubled in the composed case, indicating
proper transparency of the operations.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Correctness}

The most obvious test to perform is a correctness test.  It is
important to ensure that the reported operation counts give an
accurate representation of the actions performed by the program.
Unfortunately it is difficult to do this type of test for anything but
a trivial case.

The entire motivation behind implementing operation counting adaptors
is that it is difficult to determine from looking at an algorithm
exactly what operations are invoked.  It is easy to miss subtle,
implicit calls to constructors, conversion operators and the like.
Thus, the only correctness tests that can be readily performed are
simple examples where it is immediately clear from a visual inspection
of the code what is happening.

This code is centered around a function that performs one call to each
of several operations.

@d correctness test basis function 
@{void do_operations () {
  @<correctness test \verb|value_counter| operations@>
  @<correctness test \verb|iterator_counter| operations@>
  @<correctness test \verb|difference_counter| operations@>
  @<correctness test \verb|unary_function_counter| operations@>
  @<correctness test \verb|binary_function_counter| operations@>
}
@}

@d correctness test \verb|value_counter| operations 
@{value_counter<int> vc;  // default ctor
vc = value_counter<int>(vc);  // assignment, copy ctor
vc++;  // post-increment
// 2 object dtors, 2 implicit dtors in post-increment
@}

@d correctness test \verb|iterator_counter| operations 
@{iterator_counter<int*> ic;  // default ctor
ic = iterator_counter<int*>(ic);  // assignment, copy ctor
ic++;  // post-increment
// 2 object dtors, 2 implicit dtors in post-increment
@}

@d correctness test \verb|difference_counter| operations 
@{difference_counter<size_t, int*> dc;  // default ctor
// assignment, copy ctor
dc = difference_counter<size_t, int*>(dc);
dc++;  // post-increment
// 2 object dtors, 2 implicit dtors in post-increment
@}

@d correctness test \verb|unary_function_counter| operations 
@{identity<int> id;
unary_function_counter<identity<int> > ufc(id);  // other ctor
// assignment, copy ctor
ufc = unary_function_counter<identity<int> >(ufc);
ufc(0);  // function call
// 2 object dtors
@}

@d correctness test \verb|binary_function_counter| operations 
@{equal_to<int> eq;
binary_function_counter<equal_to<int> > bfc(eq);  // other ctor
// assignment, copy ctor
bfc = binary_function_counter<equal_to<int> >(bfc);
bfc(0, 0);  // function call
// 2 object dtors
@}

This basis function is then invoked repeatedly.  Given a number, $N$,
for each integer $i < N$ the function is called $i$ times and the
counts are recorded.  Thus, assuming the counting is working properly,
the \verb|recorder| should contain snapshots with 1, 2, 3, ... $N$ as
the operation counts.  The \verb|recorder|'s reporting function is
then called to print median, minimum and maximum operation counts.

Of course, if the iterations are performed in order (1, 2, 3, ... $N$)
the work of the \verb|recorder|'s evaluation functions is trivial.
Thus, their order is randomized.

@d correctness test iteration randomization 
@{vector<size_t> ni(N);
iota(ni.begin(), ni.end(), 1);
random_shuffle(ni.begin(), ni.end());
@}

@d correctness test iterations 
@{recorder<> r;
for (size_t i = 0; i < ni.size(); ++i) {
  for (size_t j = 0; j < ni[i]; ++j)
    do_operations();
  r.record();
}
r.report_headings(cout);
r.report_table(cout,
               &median_element<counter_vector<>::const_iterator>);
r.report_table(cout,
               &min_element<counter_vector<>::const_iterator>);
r.report_table(cout, 
               &max_element<counter_vector<>::const_iterator>);
@}

@o test-corr.cc -d 
@{#include <iostream>
#include "counters.h"

@<correctness test basis function@>

int main() {
  size_t N = 10;
  @<correctness test iteration randomization@>
  @<correctness test iterations@>
}
@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{9}
  \bibitem{musser:timing} D. R. Musser.  Measuring Computing Times of
  Generic Algorithms.  December, 1996.

  \bibitem{musser:introsort} D. R. Musser. `Introspective
  Sorting and Selection Algorithms'.  \textit{Software --- Practice
  and Experience}, \textbf{27}(8), 983-993 (August 1997).
\end{thebibliography}

\end{document}

@o recorder.eps 
@{%!PS-Adobe-2.0 EPSF-2.0
%%Title: recorder.eps
%%Creator: fig2dev Version 3.2 Patchlevel 1
%%CreationDate: Wed Dec  2 12:06:11 1998
%%For: Josh Wilmes
%%Orientation: Portrait
%%BoundingBox: 0 0 259 175
%%Pages: 0
%%BeginSetup
%%EndSetup
%%Magnification: 0.5000
%%EndComments
/$F2psDict 200 dict def
$F2psDict begin
$F2psDict /mtrx matrix put
/col-1 {0 setgray} bind def
/col0 {0.000 0.000 0.000 srgb} bind def
/col1 {0.000 0.000 1.000 srgb} bind def
/col2 {0.000 1.000 0.000 srgb} bind def
/col3 {0.000 1.000 1.000 srgb} bind def
/col4 {1.000 0.000 0.000 srgb} bind def
/col5 {1.000 0.000 1.000 srgb} bind def
/col6 {1.000 1.000 0.000 srgb} bind def
/col7 {1.000 1.000 1.000 srgb} bind def
/col8 {0.000 0.000 0.560 srgb} bind def
/col9 {0.000 0.000 0.690 srgb} bind def
/col10 {0.000 0.000 0.820 srgb} bind def
/col11 {0.530 0.810 1.000 srgb} bind def
/col12 {0.000 0.560 0.000 srgb} bind def
/col13 {0.000 0.690 0.000 srgb} bind def
/col14 {0.000 0.820 0.000 srgb} bind def
/col15 {0.000 0.560 0.560 srgb} bind def
/col16 {0.000 0.690 0.690 srgb} bind def
/col17 {0.000 0.820 0.820 srgb} bind def
/col18 {0.560 0.000 0.000 srgb} bind def
/col19 {0.690 0.000 0.000 srgb} bind def
/col20 {0.820 0.000 0.000 srgb} bind def
/col21 {0.560 0.000 0.560 srgb} bind def
/col22 {0.690 0.000 0.690 srgb} bind def
/col23 {0.820 0.000 0.820 srgb} bind def
/col24 {0.500 0.190 0.000 srgb} bind def
/col25 {0.630 0.250 0.000 srgb} bind def
/col26 {0.750 0.380 0.000 srgb} bind def
/col27 {1.000 0.500 0.500 srgb} bind def
/col28 {1.000 0.630 0.630 srgb} bind def
/col29 {1.000 0.750 0.750 srgb} bind def
/col30 {1.000 0.880 0.880 srgb} bind def
/col31 {1.000 0.840 0.000 srgb} bind def

end
save
-8.0 183.0 translate
1 -1 scale

/cp {closepath} bind def
/ef {eofill} bind def
/gr {grestore} bind def
/gs {gsave} bind def
/sa {save} bind def
/rs {restore} bind def
/l {lineto} bind def
/m {moveto} bind def
/rm {rmoveto} bind def
/n {newpath} bind def
/s {stroke} bind def
/sh {show} bind def
/slc {setlinecap} bind def
/slj {setlinejoin} bind def
/slw {setlinewidth} bind def
/srgb {setrgbcolor} bind def
/rot {rotate} bind def
/sc {scale} bind def
/sd {setdash} bind def
/ff {findfont} bind def
/sf {setfont} bind def
/scf {scalefont} bind def
/sw {stringwidth} bind def
/tr {translate} bind def
/tnt {dup dup currentrgbcolor
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb}
  bind def
/shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
  4 -2 roll mul srgb} bind def
/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
/$F2psEnd {$F2psEnteredState restore end} def
%%EndProlog

$F2psBegin
10 setmiterlimit
n -1000 6790 m -1000 -1000 l 9472 -1000 l 9472 6790 l cp clip
 0.03150 0.03150 sc
% Polyline
7.500 slw
n 5839 292 m 7695 292 l 7695 960 l 5839 960 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2126 292 m 3984 292 l 3984 960 l 2126 960 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 3984 292 m 5839 292 l 5839 960 l 3984 960 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 3984 1628 m 5839 1628 l 5839 2296 l 3984 2296 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 3984 2964 m 5839 2964 l 5839 3632 l 3984 3632 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 270 292 m 2126 292 l 2126 960 l 270 960 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 270 1628 m 2126 1628 l 2126 2296 l 270 2296 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 270 960 m 2126 960 l 2126 1628 l 270 1628 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 270 2296 m 2126 2296 l 2126 2964 l 270 2964 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 270 2964 m 2126 2964 l 2126 3632 l 270 3632 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 270 3632 m 2126 3632 l 2126 4300 l 270 4300 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 270 4300 m 2126 4300 l 2126 4968 l 270 4968 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 3984 4300 m 5839 4300 l 5839 4968 l 3984 4968 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2126 4300 m 3984 4300 l 3984 4968 l 2126 4968 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2126 3632 m 3984 3632 l 3984 4300 l 2126 4300 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2126 2964 m 3984 2964 l 3984 3632 l 2126 3632 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2126 2296 m 3984 2296 l 3984 2964 l 2126 2964 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2126 1628 m 3984 1628 l 3984 2296 l 2126 2296 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2126 960 m 3984 960 l 3984 1628 l 2126 1628 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 3984 960 m 5839 960 l 5839 1628 l 3984 1628 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 3984 2296 m 5839 2296 l 5839 2964 l 3984 2964 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 3984 3632 m 5839 3632 l 5839 4300 l 3984 4300 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 5839 4300 m 7695 4300 l 7695 4968 l 5839 4968 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 5839 3632 m 7695 3632 l 7695 4300 l 5839 4300 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 5839 2964 m 7695 2964 l 7695 3632 l 5839 3632 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 5839 2296 m 7695 2296 l 7695 2964 l 5839 2964 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 5839 1628 m 7695 1628 l 7695 2296 l 5839 2296 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 5839 960 m 7695 960 l 7695 1628 l 5839 1628 l cp gs col7 1.00 shd ef gr gs col0 s gr 
/Courier-Bold ff 165.00 scf sf
4050 720 m
gs 1 -1 sc (difference_counter) col0 sh gr
/Courier-Bold ff 165.00 scf sf
2250 720 m
gs 1 -1 sc (iterator_counter) col0 sh gr
/Courier-Bold ff 165.00 scf sf
6120 720 m
gs 1 -1 sc (value_counter) col0 sh gr
/Courier-Bold ff 165.00 scf sf
540 4050 m
gs 1 -1 sc (POST_INCREMENT) col0 sh gr
/Courier-Bold ff 165.00 scf sf
540 2700 m
gs 1 -1 sc (EQUALITY) col0 sh gr
/Courier-Bold ff 165.00 scf sf
540 2025 m
gs 1 -1 sc (COPY_CTOR) col0 sh gr
/Courier-Bold ff 165.00 scf sf
540 1350 m
gs 1 -1 sc (DEFAULT_CTOR) col0 sh gr
/Courier-Bold ff 165.00 scf sf
540 4680 m
gs 1 -1 sc (PLUS_ASSIGN) col0 sh gr
/Courier-Bold ff 165.00 scf sf
540 3330 m
gs 1 -1 sc (PLUS) col0 sh gr
% Polyline
n 6199 697 m 8055 697 l 8055 1365 l 6199 1365 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2486 697 m 4344 697 l 4344 1365 l 2486 1365 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 4344 697 m 6199 697 l 6199 1365 l 4344 1365 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 4344 2033 m 6199 2033 l 6199 2701 l 4344 2701 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 4344 3369 m 6199 3369 l 6199 4037 l 4344 4037 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 630 697 m 2486 697 l 2486 1365 l 630 1365 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 630 2033 m 2486 2033 l 2486 2701 l 630 2701 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 630 1365 m 2486 1365 l 2486 2033 l 630 2033 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 630 2701 m 2486 2701 l 2486 3369 l 630 3369 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 630 3369 m 2486 3369 l 2486 4037 l 630 4037 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 630 4037 m 2486 4037 l 2486 4705 l 630 4705 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 630 4705 m 2486 4705 l 2486 5373 l 630 5373 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 4344 4705 m 6199 4705 l 6199 5373 l 4344 5373 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2486 4705 m 4344 4705 l 4344 5373 l 2486 5373 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2486 4037 m 4344 4037 l 4344 4705 l 2486 4705 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2486 3369 m 4344 3369 l 4344 4037 l 2486 4037 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2486 2701 m 4344 2701 l 4344 3369 l 2486 3369 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2486 2033 m 4344 2033 l 4344 2701 l 2486 2701 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2486 1365 m 4344 1365 l 4344 2033 l 2486 2033 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 4344 1365 m 6199 1365 l 6199 2033 l 4344 2033 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 4344 2701 m 6199 2701 l 6199 3369 l 4344 3369 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 4344 4037 m 6199 4037 l 6199 4705 l 4344 4705 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 6199 4705 m 8055 4705 l 8055 5373 l 6199 5373 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 6199 4037 m 8055 4037 l 8055 4705 l 6199 4705 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 6199 3369 m 8055 3369 l 8055 4037 l 6199 4037 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 6199 2701 m 8055 2701 l 8055 3369 l 6199 3369 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 6199 2033 m 8055 2033 l 8055 2701 l 6199 2701 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 6199 1365 m 8055 1365 l 8055 2033 l 6199 2033 l cp gs col7 1.00 shd ef gr gs col0 s gr 
/Courier-Bold ff 165.00 scf sf
4410 1125 m
gs 1 -1 sc (difference_counter) col0 sh gr
/Courier-Bold ff 165.00 scf sf
2610 1125 m
gs 1 -1 sc (iterator_counter) col0 sh gr
/Courier-Bold ff 165.00 scf sf
6480 1125 m
gs 1 -1 sc (value_counter) col0 sh gr
/Courier-Bold ff 165.00 scf sf
900 4455 m
gs 1 -1 sc (POST_INCREMENT) col0 sh gr
/Courier-Bold ff 165.00 scf sf
900 3105 m
gs 1 -1 sc (EQUALITY) col0 sh gr
/Courier-Bold ff 165.00 scf sf
900 2430 m
gs 1 -1 sc (COPY_CTOR) col0 sh gr
/Courier-Bold ff 165.00 scf sf
900 1755 m
gs 1 -1 sc (DEFAULT_CTOR) col0 sh gr
/Courier-Bold ff 165.00 scf sf
900 5085 m
gs 1 -1 sc (PLUS_ASSIGN) col0 sh gr
/Courier-Bold ff 165.00 scf sf
900 3735 m
gs 1 -1 sc (PLUS) col0 sh gr
% Polyline
n 6604 1102 m 8460 1102 l 8460 1770 l 6604 1770 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2891 1102 m 4749 1102 l 4749 1770 l 2891 1770 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 4749 1102 m 6604 1102 l 6604 1770 l 4749 1770 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 4749 2438 m 6604 2438 l 6604 3106 l 4749 3106 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 4749 3774 m 6604 3774 l 6604 4442 l 4749 4442 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 1035 1102 m 2891 1102 l 2891 1770 l 1035 1770 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 1035 2438 m 2891 2438 l 2891 3106 l 1035 3106 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 1035 1770 m 2891 1770 l 2891 2438 l 1035 2438 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 1035 3106 m 2891 3106 l 2891 3774 l 1035 3774 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 1035 3774 m 2891 3774 l 2891 4442 l 1035 4442 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 1035 4442 m 2891 4442 l 2891 5110 l 1035 5110 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 1035 5110 m 2891 5110 l 2891 5778 l 1035 5778 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 4749 5110 m 6604 5110 l 6604 5778 l 4749 5778 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2891 5110 m 4749 5110 l 4749 5778 l 2891 5778 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2891 4442 m 4749 4442 l 4749 5110 l 2891 5110 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2891 3774 m 4749 3774 l 4749 4442 l 2891 4442 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2891 3106 m 4749 3106 l 4749 3774 l 2891 3774 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2891 2438 m 4749 2438 l 4749 3106 l 2891 3106 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 2891 1770 m 4749 1770 l 4749 2438 l 2891 2438 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 4749 1770 m 6604 1770 l 6604 2438 l 4749 2438 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 4749 3106 m 6604 3106 l 6604 3774 l 4749 3774 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 4749 4442 m 6604 4442 l 6604 5110 l 4749 5110 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 6604 5110 m 8460 5110 l 8460 5778 l 6604 5778 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 6604 4442 m 8460 4442 l 8460 5110 l 6604 5110 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 6604 3774 m 8460 3774 l 8460 4442 l 6604 4442 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 6604 3106 m 8460 3106 l 8460 3774 l 6604 3774 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 6604 2438 m 8460 2438 l 8460 3106 l 6604 3106 l cp gs col7 1.00 shd ef gr gs col0 s gr 
% Polyline
n 6604 1770 m 8460 1770 l 8460 2438 l 6604 2438 l cp gs col7 1.00 shd ef gr gs col0 s gr 
/Courier-Bold ff 165.00 scf sf
4815 1530 m
gs 1 -1 sc (difference_counter) col0 sh gr
/Courier-Bold ff 165.00 scf sf
3015 1530 m
gs 1 -1 sc (iterator_counter) col0 sh gr
/Courier-Bold ff 165.00 scf sf
6885 1530 m
gs 1 -1 sc (value_counter) col0 sh gr
/Courier-Bold ff 165.00 scf sf
1305 4860 m
gs 1 -1 sc (POST_INCREMENT) col0 sh gr
/Courier-Bold ff 165.00 scf sf
1305 3510 m
gs 1 -1 sc (EQUALITY) col0 sh gr
/Courier-Bold ff 165.00 scf sf
1305 2835 m
gs 1 -1 sc (COPY_CTOR) col0 sh gr
/Courier-Bold ff 165.00 scf sf
1305 2160 m
gs 1 -1 sc (DEFAULT_CTOR) col0 sh gr
/Courier-Bold ff 165.00 scf sf
1305 5490 m
gs 1 -1 sc (PLUS_ASSIGN) col0 sh gr
/Courier-Bold ff 165.00 scf sf
1305 4140 m
gs 1 -1 sc (PLUS) col0 sh gr
/Courier-Bold ff 165.00 scf sf
1170 1350 m
gs 1 -1 sc (T=2) col0 sh gr
/Courier-Bold ff 165.00 scf sf
360 540 m
gs 1 -1 sc (T=0) col0 sh gr
/Courier-Bold ff 165.00 scf sf
765 945 m
gs 1 -1 sc (T=1) col0 sh gr
/Courier-Bold ff 165.00 scf sf
3780 2205 m
gs 1 -1 sc (0) col0 sh gr
/Courier-Bold ff 165.00 scf sf
3780 2880 m
gs 1 -1 sc (0) col0 sh gr
/Courier-Bold ff 165.00 scf sf
3780 3555 m
gs 1 -1 sc (42) col0 sh gr
/Courier-Bold ff 165.00 scf sf
3780 4185 m
gs 1 -1 sc (0) col0 sh gr
/Courier-Bold ff 165.00 scf sf
3780 4860 m
gs 1 -1 sc (54) col0 sh gr
/Courier-Bold ff 165.00 scf sf
3780 5490 m
gs 1 -1 sc (0) col0 sh gr
/Courier-Bold ff 165.00 scf sf
5580 2205 m
gs 1 -1 sc (0) col0 sh gr
/Courier-Bold ff 165.00 scf sf
5580 2880 m
gs 1 -1 sc (5) col0 sh gr
/Courier-Bold ff 165.00 scf sf
5580 3555 m
gs 1 -1 sc (0) col0 sh gr
/Courier-Bold ff 165.00 scf sf
5580 4185 m
gs 1 -1 sc (0) col0 sh gr
/Courier-Bold ff 165.00 scf sf
5580 4860 m
gs 1 -1 sc (0) col0 sh gr
/Courier-Bold ff 165.00 scf sf
5580 5490 m
gs 1 -1 sc (0) col0 sh gr
/Courier-Bold ff 165.00 scf sf
7380 2205 m
gs 1 -1 sc (0) col0 sh gr
/Courier-Bold ff 165.00 scf sf
7380 2880 m
gs 1 -1 sc (0) col0 sh gr
/Courier-Bold ff 165.00 scf sf
7380 3555 m
gs 1 -1 sc (0) col0 sh gr
/Courier-Bold ff 165.00 scf sf
7380 4185 m
gs 1 -1 sc (12) col0 sh gr
/Courier-Bold ff 165.00 scf sf
7380 4860 m
gs 1 -1 sc (0) col0 sh gr
/Courier-Bold ff 165.00 scf sf
7380 5490 m
gs 1 -1 sc (0) col0 sh gr
$F2psEnd
rs
@}