\documentclass{article}
\usepackage{color}
\definecolor{light}{gray}{.93}
\usepackage[plainpages=false,pdftex,colorlinks,backref]{hyperref}

\title{Computing Quantiles}

\author{Larry Bush}

\newcommand{\first}{\mbox{\texttt{first}}}
\newcommand{\last}{\mbox{\texttt{last}}}
\newcommand{\midpoint}{\mbox{\texttt{midpoint}}}
\newcommand{\current}{\mbox{\texttt{current}}}

\newtheorem{theorem}{Theorem}

\begin{document}

\maketitle

\begin{abstract}

%%%%%%%%%%%%%%    Abstract    %%%%%%%%%%%%%%%%%%%%%

This paper presents a generic function to compute the $m$-th quantiles of
a multiset of numbers.  It is implemented as a C++ template function.  
A test program is also presented.  This presentation is an 
adaptation and improvement of the program presented in \cite{CQV} and \cite{CQVr}.

\end{abstract}

\tableofcontents

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}

%%%%%%%%%%%    Intro    %%%%%%%%%%%%%%%%
In the referenced paper \cite{CQVr} a program is presented for calculating
the quantiles of a seqence.  

The program used a function which calculates the
interior $m$-tile of any quantity.  An $m$-tile, represents the equal division
of a sequence into parts. This is much like a quartile, but $m$-tile of a
sequence may be calculated for any scalar value.  A precise definition of
an $m$-tile along with the assumptions used in \cite{CQVr} is given in the following section.

The quantile function presented in this paper improves upon that algorithm in 
qenericity and efficiency.  These improvements are discussed in \ref{changes1} below.

The Main program presented in this paper uses the new function to compute 
quartiles as well as user defined $m$-tiles.  It also tests the function 
using several new tests.  These changes are explained in \ref{changes2}.

Instructions for compiling and running this program are included in \ref{instructions}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Definition of $m$-tiles}
\label{definition}

%%%%%%%%%%%%    Definitions    %%%%%%%%%%%%%%%%
The definition of an $m$\emph{-tile} used in this paper is the same
as that used in \cite[p.~2]{CQVr} which was
adapted from \cite[p.~361]{CRC}.

\begin{quotation}``The following definition is adapted from \cite[p.~361]{CRC}.

For a given multiset of values $S$ with $N$ elements (counting
repetitions), $V$ is called the $r$\emph{-th} $m$\emph{-tile} (or
$r$\emph{-th} $m$\emph{-tile mark}) ($r = 0, 1, \ldots, m$) if
simultaneously,
\[
      |\{x \in S: x < V\}|/N \leq r/m,
\]
and
\[
      |\{x \in S: V < x\}|/N \leq (m - r)/m.
\]
In particular, the zeroth $m$-tile is the minimum of the values and
the $m$-th $m$-tile is the maximum.\footnote{The definition given in
\cite{CRC} is more general in that it allows for weights to be
associated with the values.  The definition given here is for the special
(and most common) case in which the weights are all 1.} 

The case $m=2$ and $r=1$ defines the median value. In this case the
definition says the median is any value that satisfies both
\[
      |\{x \in S: x < V\}|/N \leq 1/2,
\]
and
\[
      |\{x \in S: V < x\}|/N \leq 1/2.
\]
Suppose now the values of the multiset $S$ are written as a sequence
in ascending order, $x_0 \leq x_1 \leq \ldots \leq x_{N-1}$. In the
case where $N$ is odd, the above inequalities determine a unique
median value, the value $x_{(N-1)/2}$ with central index $(N-1)/2 =
\lfloor N/2 \rfloor$. In the even case, there is a central pair of
values $x_{N/2 - 1}$ and $x_{N/2}$, and our definition allows the
median to be chosen as any value $V \in [x_{N/2 - 1}, x_{N/2}]$.  Many
authors define the median in this case to be the midpoint of the range
$[x_{N/2 - 1}, x_{N/2}]$, i.e., the arithmetic mean $(x_{N/2 - 1} +
x_{N/2})/2$.  But the above definition allows it to be chosen more
simply. Our $m$-tiles function computes it as $x_{N/2}$, the maximum
of the possible values.  Note that when $N$ is even, $N/2 = \lfloor
N/2 \rfloor$, so that regardless of the parity of $N$, we can compute
the median as $x_{\lfloor N/2 \rfloor}$ (provided, again, that $S$ is
in ascending order, but the basic definition of $m$-tiles doesn't
require ascending order, and we shall see that in actually computing
the quantiles we do not need to fully sort the sequence).

Let us now derive the possible choices for an index
$k$ such that $x_k$ is an $r$-th $m$-tile.  
Suppose the values of the multiset $S$ are written as a sequence
$x_0, x_1, \ldots, x_{N-1}$, and $r$ and $m$ are integers such
that $0 \leq r \leq m \leq N$.  Assume also that for some
index $k$,
\begin{enumerate}

  \item $x_p \leq x_k$ for all $p \in [0, k)$,

  \item $x_k \leq x_q$ for all $q \in [k+1, N)$.

\end{enumerate}
Then from 1, 
\[
      |\{x \in S: x < x_k\}| \leq k,
\]
and from 2, 
\[
      |\{x \in S: x_k < x\}| \leq N - k - 1.
\]
Thus for $x_k$ to be an $r$-th $m$-tile, it suffices that $k/N \leq r/m$
and $(N - k - 1)/N \leq (m-r)/m$.  The latter inequality is
equivalent to 
\begin{eqnarray*}
  1-(k+1)/N  & \leq & 1 - r/m, ~~~ \mbox{or}\\
  r/m  & \leq & (k+1)/N, ~~~ \mbox{or}\\
  rN/m & \leq & k+1
\end{eqnarray*}
Thus
\begin{equation}
      k \leq rN/m \leq k + 1.     \label{bounds}
\end{equation}
Now there are two cases, depending on whether or not $rN/m$ is an integer.
\begin{enumerate}

 \item If $rN/m$ is not an integer, we must have
\[
      k < rN/m < k + 1,
\]
and $k = \lfloor rN/m \rfloor$.  

 \item If $rN/m$ is an integer, it appears from (\ref{bounds}) that we can
take $k = rN/m$ or $k = rN/m - 1$.  Either choice is possible except in
the boundary cases: when $r = 0$, we can only choose $k = 0$; and when
$r = m$, we can only choose $k = N - 1$.  
\end{enumerate}
%
Thus a simple and consistent way of choosing $k$ is always as $\lfloor
rN/m \rfloor$, unless $r = N$, in which case we must choose $k = N -
1$.  Finally, note that when computing interior quantiles only, i.e.,
$0 < r < m$, we can always choose $k = \lfloor rN/m \rfloor$.

For handy reference, we restate the main conclusion we will use in
the showing correctness of the function in Section~\ref{function}:
\begin{theorem}
\label{quant}
Let the values of the multiset $S$ be written as a sequence
$x_0, x_1, \ldots, x_{N-1}$,  let $r$ and $m$ be integers such
that $0 \leq r < m \leq N$, and let $k = \lfloor rN/m \rfloor$.
If we furthermore have 
\[
x_p \leq x_k \leq x_q ~~\mbox{for all $p \in [0, k)$ and $q \in [k+1, N)$}
\]
then $x_k$ is an $r$-th $m$-tile of $S$.
\end{theorem}

As a simple application of this theorem, consider the case $m=4$,
where the $m$-tiles are called quartiles.  Thus the first quartile,
$Q_1$, is defined as any value $V$ that satisfies
\[
      |\{x \in S: x < V\}|/N  \leq 1/4,
\]
and
\[
      |\{x \in S: V < x\}|/N  \leq 3/4.
\]
If the values of $S$ are $x_0, x_1, \ldots, x_{N-1}$ and are ordered
such that $x_p \leq x_k \leq x_q ~~\mbox{for all $p \in [0, k)$ and $q
\in [k+1, N)$}$ where $k = {\lfloor N/4 \rfloor}$, then by the theorem
we can choose $Q_1 = x_k = x_{\lfloor N/4 \rfloor}$.''\cite{CQVr}
\end{quotation}
%%%%%%%%%%%%%%%%%    end of Definitions    %%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Changes}

I have changed the previous version \cite{CQV} of the quantiles algorithm and associated
program in several ways. 

\subsection{Changes to the Main Program}
\label{changes2}
 First of all, the program that I created to call
the quantiles function and run tests on it, also allows user input.  In creating
the user interface, I assume that the user will redirect a file to
standard input.  This file will contain a list of numbers whitespace delimited.

This file will also contain 2 other pieces of information.  The first number in the file will
indicate the $m$-tile that the user wants computed.  For example, if the first number
in the file is a 4, the program will compute the quartiles on the user's input.
The second number in the file will indicate if the user wants the program 
to output the number sequence (0 = no, 1 = yes).  If the sequence is large, then this 
is a time consuming process.  Plus, it is not helpful in determining 
the correctness of the algorithm unless the sequence is small. 
The remaining numbers are the user's input sequence.

My version also computes many more test sequences.  My program performs
a series of ``hard wired'' quartiles tests as well as tests that vary 
depending on the number of quantiles the user chooses to compute.  These tests are 
discussed below.

\subsection{Changes to the Quantiles Function}
\label{changes1}
My version also has a more efficient version of the quantiles function.
This efficiency is particularly notable when the number of quantiles is variable (and large).
The correctness, design and efficiency of this algorithm is discussed below.

My quantiles algorithm also outputs to a back insertion iterator, and
outputs iterators that point to the given quantile rather than outputting
the quantile itself.  This has the added benefit that the iterators can be
used to manipulate the quantile, iterate forward or backward in the container, 
compute the distance between the quantiles, or sort/search between 
two quantiles.

Note: I changed the quantiles calculation of so that it reflects the upper bound 
rather than the lower bound as shown in \cite{CQVr}.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Compile and Run Instructions}
\label{instructions}

\subsection{Compile Instructions}

I have included a Makefile that generates a pdf file, cpp file and an
executable file from this w file.  It also compiles the cpp file 
(using GNU C++ version 3.2 on CS Solaris Machines) and runs the executable 
on the file ``input.txt''.  The input.txt file is not included because it is large.
However, I have created an input file that is 
set up to compute $7$-tiles on 9,998 distict integers (3 - 10,000).  This combination
is used because it produces asymmetric rounding issues which would cause 
problems with a simpler divide and counquer algorithm.  The file tells
the program not to output the sequence.  

The file is located at: 
http://www.cs.rpi.edu/\~{}bushl2/files/input.txt

I also created an input file that is 
set up to compute $177$-tiles on 10,000 distict integers (1 - 10,000).  
This file also tells
the program not to output the sequence.  

That file is located at: 
http://www.cs.rpi.edu/\~{}bushl2/files/input2.txt

The program passes all tests on these seqences.

\subsection{Run Instructions}

The program can be run by typing ``./larry-quantiles''.
The program expects as input, the $m$-tile number, an indicator of 
whether or not you want the seqence to be output (1 for yes, 0 for no), and 
the sequence of numbers.

For example the input : 4 1 1 2 3 4 5 8 7 6 

would generate the quartiles of the sequence 1 - 8. It would
also output the sequence.  This first number ``4'' indicates quartiles and the 
second number ``1'' tells the program to output the sequence.

Most likely, you will prefer to redirect a file to the program.  

The command:    ./larry-quantile $<$ input.txt

will do this.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{A program that computes quantiles}


%%%%%%%%%%%%%    Explain Main Program Pieces    %%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%    main overview    %%%%%%%%%%%%%%%%%
Here is a program that demonstrates the features of the 
\texttt{quantiles} functon.  The first order of business is to
typedef and instantiate some containers.  ``D'' is the main
container.  It will store the sequence.  ``D0'' is a backup 
container.  It will allow us to restore the sequence ``D'' to
its original form, so that we can run some tests.  ``Dnew'' is 
used when we need 2 containers for our test.  ``D\_user'' is 
a container reserved to perform the final acceptance test.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%					MAIN		          %%%%%%%%%%%%%%%%
%%%%%%%%%%%%%					MAIN		          %%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part1}
\verb@"larry-quantiles.cpp"@ {\footnotesize \hypertarget{7a}{7a} }$\equiv$
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@@\\
\mbox{}\verb@#include <iostream>@\\
\mbox{}\verb@#include <vector>@\\
\mbox{}\verb@#include <iterator>@\\
\mbox{}\verb@#include <algorithm>@\\
\mbox{}\verb@#include <cassert>@\\
\mbox{}\verb@using namespace std;@\\
\mbox{}\verb@@\\
\mbox{}\verb@@\hbox{\colorbox{light}{$\langle$Define quantiles function {\footnotesize \hyperlink{9}{9}}$\rangle$}}\verb@@\\
\mbox{}\verb@@\hbox{\colorbox{light}{$\langle$Define quantiles helper function {\footnotesize \hyperlink{10a}{10a}}$\rangle$}}\verb@@\\
\mbox{}\verb@@\hbox{\colorbox{light}{$\langle$Define acceptance test function {\footnotesize \hyperlink{17a}{17a}}$\rangle$}}\verb@@\\
\mbox{}\verb@@\\
\mbox{}\verb@int main() @\\
\mbox{}\verb@{@\\
\mbox{}\verb@  typedef vector<double> container;@\\
\mbox{}\verb@  container D, D0, Dnew, D_user;@\\
\mbox{}\verb@  @\hbox{\colorbox{light}{$\langle$Read sequence of numbers from standard input into D {\footnotesize \hyperlink{7b}{7b}}$\rangle$}}\verb@@\\
\mbox{}\verb@  @\hbox{\colorbox{light}{$\langle$Save D in D0 for later checking {\footnotesize \hyperlink{13b}{13b}}$\rangle$}}\verb@@\\
\mbox{}\verb@  @\hbox{\colorbox{light}{$\langle$Output the sequence of numbers {\footnotesize \hyperlink{8}{8}}$\rangle$}}\verb@@\\
\mbox{}\verb@  @\hbox{\colorbox{light}{$\langle$Compute quartiles (4-th quantiles) {\footnotesize \hyperlink{12a}{12a}}$\rangle$}}\verb@@\\
\mbox{}\verb@  @\hbox{\colorbox{light}{$\langle$Output all 5 quartiles, including the min and max {\footnotesize \hyperlink{12c}{12c}}$\rangle$}}\verb@@\\
\mbox{}\verb@  @\hbox{\colorbox{light}{$\langle$Hard wired tests {\footnotesize \hyperlink{15}{15}}$\rangle$}}\verb@@\\
\mbox{}\verb@  @\hbox{\colorbox{light}{$\langle$Compute m tiles {\footnotesize \hyperlink{12b}{12b}}$\rangle$}}\verb@@\\
\mbox{}\verb@  @\hbox{\colorbox{light}{$\langle$Output all user specified quantiles, including the min and max {\footnotesize \hyperlink{13a}{13a}}$\rangle$}}\verb@@\\
\mbox{}\verb@  @\hbox{\colorbox{light}{$\langle$User input specific tests {\footnotesize \hyperlink{16}{16}}$\rangle$}}\verb@@\\
\mbox{}\verb@  @\hbox{\colorbox{light}{$\langle$Perform quantiles acceptance test {\footnotesize \hyperlink{18b}{18b}}$\rangle$}}\verb@@\\
\mbox{}\verb@  return 0;@\\
\mbox{}\verb@}@
\end{list}
\vspace{-2ex}
\end{minipage}\\[4ex]
\end{flushleft}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%			Read in numbers		          %%%%%%%%%%%%%%%%
%%%%%%%%%%%%%			Read in numbers		          %%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Read in the numbers:

\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part2}
\colorbox{light}{$\langle$Read sequence of numbers from standard input into D {\footnotesize \hypertarget{7b}{7b}}$\rangle\equiv$}
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@@\\
\mbox{}\verb@typedef istream_iterator<int> int_input;@\\
\mbox{}\verb@@\\
\mbox{}\verb@int_input ii(cin);@\\
\mbox{}\verb@int user_quantile = *ii;@\\
\mbox{}\verb@++ii;@\\
\mbox{}\verb@int output_the_sequence = *ii;@\\
\mbox{}\verb@  @\\
\mbox{}\verb@typedef istream_iterator<double> double_input;  @\\
\mbox{}\verb@@\\
\mbox{}\verb@for (double_input j(cin); j != double_input(); ++j) @\\
\mbox{}\verb@    D.push_back(*j);@
\end{list}
\vspace{-1ex}
\footnotesize\addtolength{\baselineskip}{-1ex}
\begin{list}{}{\setlength{\itemsep}{-\parsep}\setlength{\itemindent}{-\leftmargin}}
\item Used in part \hyperlink{7a}{7a}.
\end{list}
\end{minipage}\\[4ex]
\end{flushleft}
The following code outputs the sequence of numbers.  Note that this feature can be turned off if the 2nd 
number in the input fule is 0.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%         Output Sequence                 %%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part3}
\colorbox{light}{$\langle$Output the sequence of numbers {\footnotesize \hypertarget{8}{8}}$\rangle\equiv$}
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@@\\
\mbox{}\verb@if(output_the_sequence != 0) {@\\
\mbox{}\verb@cout << "D[0], ..., D[" << D.size() - 1 << "]:" << endl;@\\
\mbox{}\verb@copy(D.begin(), D.end(), ostream_iterator<double>(cout, " "));@\\
\mbox{}\verb@cout << "\n" << endl;@\\
\mbox{}\verb@}@
\end{list}
\vspace{-1ex}
\footnotesize\addtolength{\baselineskip}{-1ex}
\begin{list}{}{\setlength{\itemsep}{-\parsep}\setlength{\itemindent}{-\leftmargin}}
\item Used in part \hyperlink{7a}{7a}.
\end{list}
\end{minipage}\\[4ex]
\end{flushleft}
\section{The quantiles function}
\label{function}

My version of the quantiles function is presented here.
This version works as follows.  

For a given $m$-tile, $m$ quantiles must be computed.  
The quantiles function uses the C++ standard library 
\texttt{nth\_element} function to compute the $r$-th $m$-tile.

The \texttt{nth\_element} function performs in linear time.
Therefore, computing \texttt{nth\_element} $m$ times would be $O(n*m)$ time.
However, this function performs in $O(n\log m)$ time. 
It does so by only limiting the application of the \texttt{nth\_element} function
to the sub-sequences between the previously computed
quantiles in the subsequent iterations of the algorithm.  Therefore, at each recursive 
level of the algorithm, \texttt{nth\_element} operates on n elements.

Since there are $n$ operations performed at each level of the algorithm, and
the algorithm has $\log_2 m$ levels this function performs in $O(n\log_2m)$ time.

The divide and counquer strategy exploits the fact that the nth-element function
partially orders the range of elements that it operates on.

The primary operation of Nth\_element is to arrange the range $[first, last)$ 
such that the element pointed to by the iterator $n$th is the same 
as the element that would be in that position if the entire 
range [first, last) had been sorted. 

However, as a side effect, none of the elements in the range [nth, last) 
is less than any of the elements in the range [first, nth). \cite{nnnnth}

Using this property, we construct a divide and
counquer algorithm that culminates with each quantile being in its
respective position in the sequence.  

The function
outputs a sequence of back insertion iterators via a back-insertion iterator that is passed
in as a parameter.

The construction of this divide and counquer algorithm starts with the
priming quantiles function.
The quantiles function passes some new variables to the 
quantile helper function, to maintian the integrity of the calculation.  
This is necessary because in certain situations, successive rounding 
can cause the sequence to not meet the definition because there will be
too many spaces between some of the computed quantiles.

These variables are denoted with the term ``absolute'' in their name.
This means that their value is the same as it was at the beginning 
of the recursion.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%         The Quantiles Function          %%%%%%%%%%%%%%%%
%%%%%%%%%%%%%         The Quantiles Function          %%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part4}
\colorbox{light}{$\langle$Define quantiles function {\footnotesize \hypertarget{9}{9}}$\rangle\equiv$}
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@@\\
\mbox{}\verb@@\\
\mbox{}\verb@template <typename RandomAccessIterator, typename OutputIterator>@\\
\mbox{}\verb@void@\\
\mbox{}\verb@ quantiles(     RandomAccessIterator first, @\\
\mbox{}\verb@                        RandomAccessIterator last, @\\
\mbox{}\verb@                        OutputIterator result, int m )@\\
\mbox{}\verb@{@\\
\mbox{}\verb@        typedef typename iterator_traits<RandomAccessIterator>::value_type @\\
\mbox{}\verb@          value_type;@\\
\mbox{}\verb@        @\\
\mbox{}\verb@        if ( m < 2 ) { return; }@\\
\mbox{}\verb@        RandomAccessIterator absolute_first = first;@\\
\mbox{}\verb@        RandomAccessIterator absolute_last = last;@\\
\mbox{}\verb@        int absolute_m = m;@\\
\mbox{}\verb@        int base_m = 0;@\\
\mbox{}\verb@        quantiles_helper(       first, last, result, m, absolute_m, @\\
\mbox{}\verb@                                                base_m, absolute_first, absolute_last   );@\\
\mbox{}\verb@        return; @\\
\mbox{}\verb@}@
\end{list}
\vspace{-1ex}
\footnotesize\addtolength{\baselineskip}{-1ex}
\begin{list}{}{\setlength{\itemsep}{-\parsep}\setlength{\itemindent}{-\leftmargin}}
\item Used in part \hyperlink{7a}{7a}.
\end{list}
\end{minipage}\\[4ex]
\end{flushleft}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%         The Quantiles Helper Function          %%%%%%%%%%%%%
%%%%%%%%%         The Quantiles Helper Function          %%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The helper function performes most of the work.  The helper function
computes the median.  It then recursively calls itself to compute 
the median of the lower and upper half of the sequence.  An iterator
pointing to the median is output to the back insertion iterator 
between the upper and lower stages.  This is so that it is in the proper order.

Note that the median must be computed before the lower steps so that the
nth element function re-orders the list, leaving the lower numbers below
the median and the higher numbers above the median.

\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part5}
\colorbox{light}{$\langle$Define quantiles helper function {\footnotesize \hypertarget{10a}{10a}}$\rangle\equiv$}
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@@\\
\mbox{}\verb@@\\
\mbox{}\verb@template <typename RandomAccessIterator, typename OutputIterator>@\\
\mbox{}\verb@void@\\
\mbox{}\verb@ quantiles_helper(      RandomAccessIterator first, @\\
\mbox{}\verb@                RandomAccessIterator last, @\\
\mbox{}\verb@                OutputIterator result, @\\
\mbox{}\verb@                int m, int absolute_m, int base_m, @\\
\mbox{}\verb@                RandomAccessIterator absolute_first, @\\
\mbox{}\verb@                RandomAccessIterator absolute_last )@\\
\mbox{}\verb@{@\\
\mbox{}\verb@  typedef typename iterator_traits<RandomAccessIterator>::value_type @\\
\mbox{}\verb@          value_type;@\\
\mbox{}\verb@        RandomAccessIterator next;@\\
\mbox{}\verb@@\\
\mbox{}\verb@    int m_new = m/2;@\\
\mbox{}\verb@        @\hbox{\colorbox{light}{$\langle$Compute m\_{new}-tile {\footnotesize \hyperlink{10b}{10b}}$\rangle$}}\verb@@\\
\mbox{}\verb@    @\\
\mbox{}\verb@        if ( 1 < m_new ) {@\\
\mbox{}\verb@                @\hbox{\colorbox{light}{$\langle$Compute lower half {\footnotesize \hyperlink{11a}{11a}}$\rangle$}}\verb@@\\
\mbox{}\verb@        } @\\
\mbox{}\verb@        *result++ = next;@\\
\mbox{}\verb@        if ( 1 < (m - m_new) ) {@\\
\mbox{}\verb@                @\hbox{\colorbox{light}{$\langle$Compute upper half {\footnotesize \hyperlink{11b}{11b}}$\rangle$}}\verb@@\\
\mbox{}\verb@        } @\\
\mbox{}\verb@        return; @\\
\mbox{}\verb@}@\\
\mbox{}\verb@@
\end{list}
\vspace{-1ex}
\footnotesize\addtolength{\baselineskip}{-1ex}
\begin{list}{}{\setlength{\itemsep}{-\parsep}\setlength{\itemindent}{-\leftmargin}}
\item Used in part \hyperlink{7a}{7a}.
\end{list}
\end{minipage}\\[4ex]
\end{flushleft}
Note: I changed the calculation of so that it reflects the upper bound 
rather than the lower bound as shown in \cite{CQVr}.  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%        Compute m_new-tile          %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part6}
\colorbox{light}{$\langle$Compute m\_{new}-tile {\footnotesize \hypertarget{10b}{10b}}$\rangle\equiv$}
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@@\\
\mbox{}\verb@    next = absolute_first + ((absolute_last - absolute_first)*@\\
\mbox{}\verb@                        (base_m + m_new))/absolute_m; @\\
\mbox{}\verb@    nth_element(first, next, last);   @\\
\mbox{}\verb@@
\end{list}
\vspace{-1ex}
\footnotesize\addtolength{\baselineskip}{-1ex}
\begin{list}{}{\setlength{\itemsep}{-\parsep}\setlength{\itemindent}{-\leftmargin}}
\item Used in part \hyperlink{10a}{10a}.
\end{list}
\end{minipage}\\[4ex]
\end{flushleft}
This code computes the lower half of the recursion.  Note that the 
next iterator is passed to both.  However, it is not
``used'' by both.  For the lower half, it marks one position past
the end of the sequence it will consider.

The absolute variables are used to calculate the m tile number.
That calculation is done in this way to avoid the possiblility of a deleterious
rounding effect due to the recursive division.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%        Compute Lower Half          %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part7}
\colorbox{light}{$\langle$Compute lower half {\footnotesize \hypertarget{11a}{11a}}$\rangle\equiv$}
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@@\\
\mbox{}\verb@        base_m = base_m;@\\
\mbox{}\verb@        quantiles_helper(first, next, result, m_new, absolute_m, @\\
\mbox{}\verb@                        base_m, absolute_first, absolute_last);@
\end{list}
\vspace{-1ex}
\footnotesize\addtolength{\baselineskip}{-1ex}
\begin{list}{}{\setlength{\itemsep}{-\parsep}\setlength{\itemindent}{-\leftmargin}}
\item Used in part \hyperlink{10a}{10a}.
\end{list}
\end{minipage}\\[4ex]
\end{flushleft}
This code computes the upper half of the recursion.  Care must be taken
to ensure that all $m$-tiles are computed and computed correctly.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%        Compute Upper Half          %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part8}
\colorbox{light}{$\langle$Compute upper half {\footnotesize \hypertarget{11b}{11b}}$\rangle\equiv$}
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@        @\\
\mbox{}\verb@        base_m = base_m + m_new;@\\
\mbox{}\verb@        quantiles_helper(       next, last, result, m - m_new, absolute_m, @\\
\mbox{}\verb@                        base_m, absolute_first, absolute_last   );@
\end{list}
\vspace{-1ex}
\footnotesize\addtolength{\baselineskip}{-1ex}
\begin{list}{}{\setlength{\itemsep}{-\parsep}\setlength{\itemindent}{-\leftmargin}}
\item Used in part \hyperlink{10a}{10a}.
\end{list}
\end{minipage}\\[4ex]
\end{flushleft}
\section{Efficiency}
\label{efficency}
This function performs in 
$O(N \log m)$ time.  This is an improvement over the efficency of \cite{CQVr}
if $m$ is not constant.  The efficiency is gained by employing a divide and counquer stratgy where the 
\texttt{nth\_element} function
is performed only on the sub-sequences of the lower levels of the algorithm.

The \texttt{nth\_element} function performs in linear time.  In other words, 
n operations are performed at each level of the algorithm, and
the algorithm has $ \log m$ levels.  The quantiles function 
exploits the fact that the nth-element function
partially orders the range of elements that it operates on.

The primary operation of \texttt{nth\_element} is to arrange the range $[first, last)$ 
such that the element pointed to by the iterator $n$th is the same 
as the element that would be in that position if the entire 
range [first, last) had been sorted. 

However, as a side effect, none of the elements in the range [nth, last) 
is less than any of the elements in the range [first, nth). \cite{nnnnth}



Since m is halved each iteration, the number of recursions is $\log m$.
The number of operations per recursion is $O(N)$.

For example, if we compute the octiles of a sequence of 16 items, this
diagram shows how the problem is broken down, so that \texttt{nth\_element} 
operates on sub-sequences of the initial sequence.  Each operation
is $O(n)$ where n is the size of a sub-sequence of the initial sequence of size N. 
The sum of all the \texttt{nth\_element} operations at each recursive step is $O(N)$.

\begin{tabular}{|c|c|c|}
\multicolumn{3}{c}{}\\
\hline

Step	&Operations &        Sub-sequence representation\\
---------	&-------------- &        -----------------------------------\\
m = 8	&\texttt{nth\_element} &        xxxxxxxxxxxxxxxx\\
m = 4	&\texttt{nth\_element} &    xxxxxxxx        xxxxxxxx\\
m = 2	&\texttt{nth\_element} &   xxxx    xxxx    xxxx    xxxx\\
\hline
\end{tabular}

Therefore, the efficiency is $O(N \log m)$.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Computing quantiles}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%        Compute Quartiles (Main)       %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%          Verbage              %%%%%%%%%%%%%%%%%%%%%%
The interior  quantiles are computed by calling the quantiles
function.  

Note that you must instantiate Q with 1 element as a placeholder for the min element.
This is because the quantiles function is defined such that it only
computes the interior quantiles.

\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part9}
\colorbox{light}{$\langle$Compute quartiles (4-th quantiles) {\footnotesize \hypertarget{12a}{12a}}$\rangle\equiv$}
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@@\\
\mbox{}\verb@        int m = 4;@\\
\mbox{}\verb@        vector<container::iterator> Q(1);@\\
\mbox{}\verb@        quantiles(D.begin(), D.end(), back_inserter(Q), m);  @
\end{list}
\vspace{-1ex}
\footnotesize\addtolength{\baselineskip}{-1ex}
\begin{list}{}{\setlength{\itemsep}{-\parsep}\setlength{\itemindent}{-\leftmargin}}
\item Used in part \hyperlink{7a}{7a}.
\end{list}
\end{minipage}\\[4ex]
\end{flushleft}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%        Compute M tiles (Main)         %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%          Verbage              %%%%%%%%%%%%%%%%%%%%%%
The interior  m tiles are computed by calling the quantiles
function.  

\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part10}
\colorbox{light}{$\langle$Compute m tiles {\footnotesize \hypertarget{12b}{12b}}$\rangle\equiv$}
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@@\\
\mbox{}\verb@        D_user = D0;@\\
\mbox{}\verb@        vector<container::iterator> Q_user(1);@\\
\mbox{}\verb@        quantiles(D_user.begin(), D_user.end(), back_inserter(Q_user), user_quantile); @
\end{list}
\vspace{-1ex}
\footnotesize\addtolength{\baselineskip}{-1ex}
\begin{list}{}{\setlength{\itemsep}{-\parsep}\setlength{\itemindent}{-\leftmargin}}
\item Used in part \hyperlink{7a}{7a}.
\end{list}
\end{minipage}\\[4ex]
\end{flushleft}
Finally, we compute the minimum and maximum elements using generic
functions from the C++ standard library then output them along with
the interior quartiles.  We save time computing this function 
by only taking the minimum of the
first section, up to the first quartile marker.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%             Output Quartiles            %%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part11}
\colorbox{light}{$\langle$Output all 5 quartiles, including the min and max {\footnotesize \hypertarget{12c}{12c}}$\rangle\equiv$}
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@@\\
\mbox{}\verb@        Q[0] = min_element(D.begin(), Q[1]);@\\
\mbox{}\verb@        Q[m] = max_element(Q[m-2],D.end());   @\\
\mbox{}\verb@        cout << "The hard wired quartiles are: " << "\n";@\\
\mbox{}\verb@        for (int r = 0; r < m+1; ++r) @\\
\mbox{}\verb@                cout << "Q[" << r << "] = " << *(Q[r]) << "\n";@\\
\mbox{}\verb@        cout << endl; @
\end{list}
\vspace{-1ex}
\footnotesize\addtolength{\baselineskip}{-1ex}
\begin{list}{}{\setlength{\itemsep}{-\parsep}\setlength{\itemindent}{-\leftmargin}}
\item Used in part \hyperlink{7a}{7a}.
\end{list}
\end{minipage}\\[4ex]
\end{flushleft}
You can save time computing this function by only taking the minimum of the
first section, up to the first m tile marker.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%             Output Quantiles            %%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part12}
\colorbox{light}{$\langle$Output all user specified quantiles, including the min and max {\footnotesize \hypertarget{13a}{13a}}$\rangle\equiv$}
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@@\\
\mbox{}\verb@@\\
\mbox{}\verb@  Q_user[0] = min_element(D_user.begin(), Q_user[1]);@\\
\mbox{}\verb@  Q_user[user_quantile] = max_element(Q_user[user_quantile-2],D_user.end());   @\\
\mbox{}\verb@  cout << "The user specified quantiles are: " << "\n";@\\
\mbox{}\verb@  for (int r = 0; r < user_quantile+1; ++r) @\\
\mbox{}\verb@    cout << "Q_user[" << r << "] = " << *(Q_user[r]) << "\n";@\\
\mbox{}\verb@  cout << endl;@\\
\mbox{}\verb@  @
\end{list}
\vspace{-1ex}
\footnotesize\addtolength{\baselineskip}{-1ex}
\begin{list}{}{\setlength{\itemsep}{-\parsep}\setlength{\itemindent}{-\leftmargin}}
\item Used in part \hyperlink{7a}{7a}.
\end{list}
\end{minipage}\\[4ex]
\end{flushleft}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%        Save D in D0 for later checking         %%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%        %%%%%%%%
An extra variable ``D0'' is used to save the vector ``D'' so that it 
can be put back to its original form in order to run tests on the 
quantiles function.

%%%%%%       %%%%%%%%
\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part13}
\colorbox{light}{$\langle$Save D in D0 for later checking {\footnotesize \hypertarget{13b}{13b}}$\rangle\equiv$}
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@@\\
\mbox{}\verb@D0 = D;@
\end{list}
\vspace{-1ex}
\footnotesize\addtolength{\baselineskip}{-1ex}
\begin{list}{}{\setlength{\itemsep}{-\parsep}\setlength{\itemindent}{-\leftmargin}}
\item Used in part \hyperlink{7a}{7a}.
\end{list}
\end{minipage}\\[4ex]
\end{flushleft}
\section{The Test Functions}
\subsection{Hard Wired Tests}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%         Perform hard wired Consistencey Checks       %%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The following portion of the program performs consistency checks.
This is to ensure that the quantiles function conforms to its definition.  For
example we expect that $median = \lfloor N/2 \rfloor$.
It is also to ensure that the function is consistent with itself when 
computing different yet analogous quantiles.  

For example, suppose we computed
$2$-tiles (the median of a sequence), quartiles, and octiles.  
The median should be the same as the second quartile, 
the second octile should be the same as the first quartile,
and the sixth octile should be the same as the third quartile.
This should be true regardless of whether the size of the sequence is even or odd.  

For our function, we also need to test the position of the iterator as
well as the value it points to.  To test for the value, we perform the above tests
on separate containers and check that the values $x == y$.  However, when we test the
consistency of the iterator, we perfrom the above tests on the same container
and expect that for a given value $\&*x == \&*y$.  In other words the iterators
are equivalent.  

\begin{itemize}
\item Test 1 is an iterator test to see if quartile and 2-tile are consistent.
\item Test 2 is an iterator test to see if quartile and 8-tile are consistent.
\item Test 3 is a value test to see if quartile and 2-tile are consistent.
\item Test 4 is a value test to see if quartile and 8-tile are consistent.
\item Test 6 determines if the distances between each quantile vary by more than 1. If they do 
not, then, in that respect, the result complies with the definition of a quantile stated above.
\end{itemize}

\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part14}
\colorbox{light}{$\langle$Hard wired tests {\footnotesize \hypertarget{15}{15}}$\rangle\equiv$}
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@@\\
\mbox{}\verb@//Test 1@\\
\mbox{}\verb@D = D0;@\\
\mbox{}\verb@vector<container::iterator> R(1);@\\
\mbox{}\verb@quantiles(D.begin(), D.end(), back_inserter(R), 2);@\\
\mbox{}\verb@assert (R[1] == Q[2]);@\\
\mbox{}\verb@cout<<"Passed Test 1";@\\
\mbox{}\verb@@\\
\mbox{}\verb@//Test 2@\\
\mbox{}\verb@D = D0;@\\
\mbox{}\verb@vector<container::iterator> S(1);@\\
\mbox{}\verb@quantiles(D.begin(), D.end(), back_inserter(S), 8);@\\
\mbox{}\verb@assert (S[2] == Q[1]);@\\
\mbox{}\verb@assert (S[4] == Q[2]);@\\
\mbox{}\verb@assert (S[6] == Q[3]);@\\
\mbox{}\verb@cout<<"Passed Test 2\n";@\\
\mbox{}\verb@@\\
\mbox{}\verb@//Test 3@\\
\mbox{}\verb@Dnew = D0;@\\
\mbox{}\verb@vector<container::iterator> T(1);@\\
\mbox{}\verb@quantiles(Dnew.begin(), Dnew.end(), back_inserter(T), 2);@\\
\mbox{}\verb@assert ( *(T[1]) == *(Q[2]) );@\\
\mbox{}\verb@cout<<"Passed Test 3\n";@\\
\mbox{}\verb@ @\\
\mbox{}\verb@//Test 4@\\
\mbox{}\verb@Dnew = D0;@\\
\mbox{}\verb@vector<container::iterator> U(1);@\\
\mbox{}\verb@quantiles(Dnew.begin(), Dnew.end(), back_inserter(U), 8);@\\
\mbox{}\verb@assert (*(U[2]) == *(Q[1]));@\\
\mbox{}\verb@assert (*(U[4]) == *(Q[2]));@\\
\mbox{}\verb@assert (*(U[6]) == *(Q[3]));@\\
\mbox{}\verb@cout<<"Passed Test 4\n";@\\
\mbox{}\verb@ @\\
\mbox{}\verb@//Test 5@\\
\mbox{}\verb@Dnew = D0;@\\
\mbox{}\verb@vector<container::iterator> V(1);@\\
\mbox{}\verb@quantiles(Dnew.begin(), Dnew.end(), back_inserter(V), 12);@\\
\mbox{}\verb@assert (*(V[3]) == *(Q[1]));@\\
\mbox{}\verb@assert (*(V[6]) == *(Q[2]));@\\
\mbox{}\verb@assert (*(V[9]) == *(Q[3]));@\\
\mbox{}\verb@cout<<"Passed Test 5\n";@\\
\mbox{}\verb@@\\
\mbox{}\verb@//Test 6@\\
\mbox{}\verb@int i;@\\
\mbox{}\verb@int high = Q[1]-Q[0];@\\
\mbox{}\verb@int low =  Q[1]-Q[0];@\\
\mbox{}\verb@int size = (Q.end()) - (Q.begin());@\\
\mbox{}\verb@for ( i = 2; i < size ; i++ ) {@\\
\mbox{}\verb@    high = max( Q[i]-Q[i-1], high );@\\
\mbox{}\verb@    low  = min( Q[i]-Q[i-1], low );@\\
\mbox{}\verb@}@\\
\mbox{}\verb@assert ( (high - low) < 2 );@\\
\mbox{}\verb@cout<<"Passed Test 6\n";@\\
\mbox{}\verb@cout << "Hard wired consistency checks passed." << endl;@\\
\mbox{}\verb@@\\
\mbox{}\verb@@
\end{list}
\vspace{-1ex}
\footnotesize\addtolength{\baselineskip}{-1ex}
\begin{list}{}{\setlength{\itemsep}{-\parsep}\setlength{\itemindent}{-\leftmargin}}
\item Used in part \hyperlink{7a}{7a}.
\end{list}
\end{minipage}\\[4ex]
\end{flushleft}
\subsection{User input dependent Tests}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%     Perform user input specific consistency checks     %%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The following portion of the program performs consistency checks
on the quantiles function that are dependent on the user's input.  This allows additional
testing using different quantiles.

These test both the position of the iterator (run on the same containers), 
as well as the
value that the iterator points to (run on separate containers) .

\begin{itemize}
\item Test 7 is a value test.  It checks up to 10 $m$-tile points in 10 other quartile 
computations on the given sequence.
\item Test 8 determines if the distances between each quantile in the user
specified $m$-tile computation vary by more than 1.  If they do 
not, then the result complies with the definition of a quantile stated above.
\end{itemize}

\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part15}
\colorbox{light}{$\langle$User input specific tests {\footnotesize \hypertarget{16}{16}}$\rangle\equiv$}
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@@\\
\mbox{}\verb@//Test 7@\\
\mbox{}\verb@for (int n = 2; n < 12; n++) {@\\
\mbox{}\verb@@\\
\mbox{}\verb@        Dnew = D0;@\\
\mbox{}\verb@        vector<container::iterator> Uu(1);@\\
\mbox{}\verb@        quantiles(Dnew.begin(), Dnew.end(), back_inserter(Uu), user_quantile*n);@\\
\mbox{}\verb@@\\
\mbox{}\verb@        for (int p = 1; p < 10; p++) {@\\
\mbox{}\verb@@\\
\mbox{}\verb@                if ( p < user_quantile ) {@\\
\mbox{}\verb@                        assert (*(Uu[p*n]) == *(Q_user[p]));@\\
\mbox{}\verb@                }@\\
\mbox{}\verb@        }@\\
\mbox{}\verb@        cout<<"Passed user specific Test 7 - "<<n<<"\n";@\\
\mbox{}\verb@@\\
\mbox{}\verb@}@\\
\mbox{}\verb@//Test 8@\\
\mbox{}\verb@high = Q_user[1]-Q_user[0];@\\
\mbox{}\verb@low =  Q_user[1]-Q_user[0];@\\
\mbox{}\verb@size = (Q_user.end()) - (Q_user.begin());@\\
\mbox{}\verb@for ( i = 2; i < size ; i++ ) {@\\
\mbox{}\verb@    high = max( Q_user[i]-Q_user[i-1], high );@\\
\mbox{}\verb@    low  = min( Q_user[i]-Q_user[i-1], low );@\\
\mbox{}\verb@}@\\
\mbox{}\verb@assert ( (high - low) < 2 );@\\
\mbox{}\verb@cout<<"Passed Test 8\n";@\\
\mbox{}\verb@  @\\
\mbox{}\verb@cout << "User input specific tests passed." << endl;@
\end{list}
\vspace{-1ex}
\footnotesize\addtolength{\baselineskip}{-1ex}
\begin{list}{}{\setlength{\itemsep}{-\parsep}\setlength{\itemindent}{-\leftmargin}}
\item Used in part \hyperlink{7a}{7a}.
\end{list}
\end{minipage}\\[4ex]
\end{flushleft}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%     Perform Acceptance Test                            %%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Acceptance Test}

The following acceptance test is a minor adaptation of the acceptance
test presented in \cite{CQVr}.  Although the above tests check for everything
that was expected of the function as presented in \cite{CQV}, a minor error in 
that function was discovered, which was corrected and the following new accepatance
test was created in \cite{CQVr} to test for this.  The main thing that this 
acceptance test check for (that the above tests do not check for) is the relative size of 
the quantiles (upper versus).  This test ensures that the quantiles produced
comply with the above definition by directly check the requirements for being
an $r$-th $m$-tile, for all of the $m$-tiles in $Q$.  

Note that the acceptance test is to be run on the saved sequence
\texttt{D0} and $Q$ via iterators.

The test function was addapted to my implementation by dereferencing Q twice.
This produces the value which is then used by count\_if to do the necessary test.

\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part16}
\colorbox{light}{$\langle$Define acceptance test function {\footnotesize \hypertarget{17a}{17a}}$\rangle\equiv$}
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@@\\
\mbox{}\verb@template <typename RandomAccessIterator, typename InputIterator>@\\
\mbox{}\verb@bool check_quantiles(RandomAccessIterator first, @\\
\mbox{}\verb@                     RandomAccessIterator last, @\\
\mbox{}\verb@                     InputIterator qfirst, InputIterator qlast, @\\
\mbox{}\verb@                     int m0)@\\
\mbox{}\verb@{@\\
\mbox{}\verb@  typedef typename iterator_traits<RandomAccessIterator>::value_type @\\
\mbox{}\verb@          value_type;@\\
\mbox{}\verb@  @\hbox{\colorbox{light}{$\langle$Define needed types and variables {\footnotesize \hyperlink{17b}{17b}}$\rangle$}}\verb@@\\
\mbox{}\verb@  @\hbox{\colorbox{light}{$\langle$Check each of the $m$-tiles {\footnotesize \hyperlink{18a}{18a}}$\rangle$}}\verb@@\\
\mbox{}\verb@  return true;@\\
\mbox{}\verb@}@
\end{list}
\vspace{-1ex}
\footnotesize\addtolength{\baselineskip}{-1ex}
\begin{list}{}{\setlength{\itemsep}{-\parsep}\setlength{\itemindent}{-\leftmargin}}
\item Used in part \hyperlink{7a}{7a}.
\end{list}
\end{minipage}\\[4ex]
\end{flushleft}
\begin{quotation}``We cast the sequence length to a \texttt{double} so that later
divisions by, or into, integers will be done using floating point 
arithmetic rather than integer arithmetic. We do the same for the
value $m$.''\cite{CQVr}
\end{quotation}

\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part17}
\colorbox{light}{$\langle$Define needed types and variables {\footnotesize \hypertarget{17b}{17b}}$\rangle\equiv$}
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@@\\
\mbox{}\verb@double N = static_cast<double>(last - first);@\\
\mbox{}\verb@double m = static_cast<double>(m0);@\\
\mbox{}\verb@int r = 0;@
\end{list}
\vspace{-1ex}
\footnotesize\addtolength{\baselineskip}{-1ex}
\begin{list}{}{\setlength{\itemsep}{-\parsep}\setlength{\itemindent}{-\leftmargin}}
\item Used in part \hyperlink{17a}{17a}.
\end{list}
\end{minipage}\\[4ex]
\end{flushleft}
\begin{quotation}``The variable $r$ keeps track of which quantile we are checking.  In
checking each quantile, we use the generic algorithm
\texttt{count\_if} from the standard library to count the elements in
the range that satisfy the predicate given as \texttt{count\_if}'s
last argument.  We construct the appropriate predicates using function
objects and function object adaptors from the standard library.''\cite{CQVr}
\end{quotation}
\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part18}
\colorbox{light}{$\langle$Check each of the $m$-tiles {\footnotesize \hypertarget{18a}{18a}}$\rangle\equiv$}
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@@\\
\mbox{}\verb@for (InputIterator i = qfirst; i != qlast; ++i, ++r) {@\\
\mbox{}\verb@  int c_less = @\\
\mbox{}\verb@     count_if(first, last, bind2nd(less<value_type>(),**i));@\\
\mbox{}\verb@  int c_greater = @\\
\mbox{}\verb@     count_if(first, last, bind2nd(greater<value_type>(), **i));@\\
\mbox{}\verb@  if (!(c_less/N <= r/m)) {@\\
\mbox{}\verb@    cout << "Test fails: r = " << r << "; c_less = " << c_less@\\
\mbox{}\verb@         << "; r/m = " << r/m @\\
\mbox{}\verb@         << "; c_less/N = " << c_less/N << endl;@\\
\mbox{}\verb@    return false;@\\
\mbox{}\verb@  }@\\
\mbox{}\verb@  if (!(c_greater/N <= (m-r)/m)) {@\\
\mbox{}\verb@    cout << "Test fails: r = " << r << "; c_greater = " << c_greater@\\
\mbox{}\verb@         << "; (m-r)/m = " << (m-r)/m @\\
\mbox{}\verb@         << "; c_greater/N = " << c_greater/N << endl;@\\
\mbox{}\verb@    return false;@\\
\mbox{}\verb@  }@\\
\mbox{}\verb@}@
\end{list}
\vspace{-1ex}
\footnotesize\addtolength{\baselineskip}{-1ex}
\begin{list}{}{\setlength{\itemsep}{-\parsep}\setlength{\itemindent}{-\leftmargin}}
\item Used in part \hyperlink{17a}{17a}.
\end{list}
\end{minipage}\\[4ex]
\end{flushleft}
This code is inserted into the main program to perform the acceptance test.

Note that Q\_user is the output sequence tested.  Q\_user is a vector of iterators
which points to D\_user.  D\_user is a container set aside specifically for this test.

\begin{flushleft} \small
\begin{minipage}{\linewidth}\color{blue} \label{part19}
\colorbox{light}{$\langle$Perform quantiles acceptance test {\footnotesize \hypertarget{18b}{18b}}$\rangle\equiv$}
\vspace{-1ex}
\begin{list}{}{} \item
\mbox{}\verb@@\\
\mbox{}\verb@if (check_quantiles(D0.begin(), D0.end(), (Q_user.begin()), (Q_user.end()), user_quantile)) {@\\
\mbox{}\verb@  std::cout << "Result passes the acceptance test\n" << std::endl;@\\
\mbox{}\verb@  return 0;@\\
\mbox{}\verb@} else {@\\
\mbox{}\verb@  std::cout << "Result doesn't pass the acceptance test!\n" @\\
\mbox{}\verb@            << std::endl;@\\
\mbox{}\verb@  return 1;}@
\end{list}
\vspace{-1ex}
\footnotesize\addtolength{\baselineskip}{-1ex}
\begin{list}{}{\setlength{\itemsep}{-\parsep}\setlength{\itemindent}{-\leftmargin}}
\item Used in part \hyperlink{7a}{7a}.
\end{list}
\end{minipage}\\[4ex]
\end{flushleft}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%                 Bibliography                  %%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{9}

 \bibitem{CQV} D. R. Musser, ``Computing Quantiles, Version 1,'' 
\emph{Generic Software Design Course Website},
http://www.cs.rpi.edu/\~{}musser/gsd/quartiles/quartiles.pdf (September 2002).

 \bibitem{CQVr} D. R. Musser, ``Computing Quantiles, Version 1, Revision 1,'' 
\emph{Generic Software Design Course Website},
http://www.cs.rpi.edu/\~{}musser/gsd/quantiles/quantiles.w (October 2002).

 \bibitem{CRC} \textsl{C. R. C. Standard Mathematical Tables, Eleventh
Edition}, C. D. Hodgman, editor-in-chief, Chemical Rubber Publishing
Co., Cleveland, Ohio, 1957.

 \bibitem{introsort} D. R. Musser, ``Introspective Sorting and
Selection Algorithms,'' \emph{Software---Practice and Experience},
Vol. 27(8), 983--993 (August 1997).

 \bibitem{nnnnth} Silicon Graphics, Inc., ``Standard 
 Template Library Programmer's Guide,'' \emph{Silicon Graphics, Inc. Website}, 
http://www.sgi.com/tech/stl/nth\_element.html (1993-2002).

\end{thebibliography}

\end{document}

