%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%  sort_vector.tex       LiDIA documentation
%%
%%  This file contains the documentation of the vector classes
%%
%%  Copyright   (c)   1995   by  LiDIA-Group
%%
%%  Authors: Frank Lehmann, Markus Maurer
%%           Patrick Theobald, Stefan Neis
%%

\newcommand{\DEF}{\textcode{\itshape DEF}}


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

\NAME

\CLASS{sort_vector< T >} \dotfill vectors with sort functions


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

\ABSTRACT

Class \code{sort_vector< T >} contains \code{base_vector< T >} as a base class.  It supports any
member and friend function of that class.  Additionally it provides functions for sorting and
searching, inserting and deleting.  \code{T} can be either a built-in type or a class.


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

\DESCRIPTION

A variable of type \code{sort_vector< T >} contains the same components as a variable of type
\code{base_vector< T >}.  In addition there is a character \code{sort_dir} and a function
pointer \code{*el_cmp}.

A vector of type \code{sort_vector< T >} can be sorted according to a certain sort direction.
This class provides two standard directions \code{SORT_VECTOR_UP} and \code{SORT_VECTOR_DOWN} to
sort the elements of a vector in ascending or descending order, respectively.  Furthermore,
specific compare functions may be used to define a relation of elements of type \code{T}.  These
functions define a new sort relation for a vector.

Any compare function used must have a prototye like
\begin{quote}
  \code{int cmp ( const T & $a$, const T & $b$ ) }.
\end{quote}
The data type for pointers to functions of that type will be called \code{CMP_FUNC} in the
sequel.  The return value of a comparison shall be as follows:
\begin{center}
  \begin{tabular}{rl}
    $ < 0 $ & if \code{(a, b)} is in correct order \\
    $ = 0 $ & if \code{a, b}  are identical      \\
    $ > 0 $ & if \code{(a, b)} is in inverted order
  \end{tabular}
\end{center}  
Any vector $v$ of type \code{sort_vector< T >} contains a default sort direction according to
which it will be sorted if the function \code{$v$.sort()} is applied.  This default sort
direction will be set to \code{SORT_VECTOR_UP} by any constructor in this class; i.e. vector $v$
will be sorted in ascending order by default.  This default value may later be changed for a
vector $v$ by using the function \code{$v$.set_sort_direction()}.


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

\CONS

Each of the following constructors can get an additional parameter (\code{FIXED} or
\code{EXPAND}) to indicate the mode of the \code{sort_vector}.

\begin{fcode}{ct}{sort_vector< T >}{}
  constructs a vector with capacity 0.
\end{fcode}

\begin{fcode}{ct}{sort_vector< T >}{lidia_size_t $c$}
  constructs a vector with capacity $c$ initialized with values generated by the default
  constructor for type \code{T}.
\end{fcode}

\begin{fcode}{ct}{sort_vector< T >}{lidia_size_t $c$, lidia_size_t $s$}
  constructs a vector with capacity $c$ and size $s$ initialized with values generated by the
  default constructor for type \code{T}.
\end{fcode}

\begin{fcode}{ct}{sort_vector< T >}{const sort_vector< T > & $w$}
  constructs a vector with capacity $w.size$ initialized with the elements of $w$.
\end{fcode}

\begin{fcode}{ct}{sort_vector< T >}{const T * $a$, lidia_size_t $l$}
  constructs a vector with capacity $l$ and size $l$ initialized with the first $l$ elements of
  the array $a$.
\end{fcode}

\begin{fcode}{dt}{~sort_vector< T >}{}
\end{fcode}


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

\STITLE{Sort direction}

\begin{cfcode}{char}{$v$.sort_direction}{}
  returns the default sort direction of vector $v$.  The return value will be one of the
  predefined constants \code{SORT_VECTOR_UP}, \code{SORT_VECTOR_UP} or \code{SORT_VECTOR_CMP}.
  The latter indicates that the sort direction of $v$ has been set to a certain compare
  function.
\end{cfcode}

\begin{cfcode}{char}{$v$.get_sort_direction}{}
  returns the default sort direction of vector $v$.  The return value will be one of the
  predefined constants \code{SORT_VECTOR_UP}, \code{SORT_VECTOR_DOWN} or \code{SORT_VECTOR_CMP}.
  The latter indicates that the sort direction of $v$ has been set to a certain compare
  function.
\end{cfcode}

\begin{fcode}{void}{$v$.set_sort_direction}{char $\mathit{dir}$}
  sets the default sort-direction for $v$ to $\mathit{dir}$.  The value of $\mathit{dir}$ may be
  either one of the two predefined constants \code{SORT_VECTOR_UP} or \code{SORT_VECTOR_DOWN}.
  If $\mathit{dir}$ is invalid, the standard sort direction of $v$ will be left unchanged and
  the \LEH will be invoked.
\end{fcode}

\begin{fcode}{void}{$v$.set_sort_direction}{int (*cmp) (const T & $a$, const T & $b$)}
  sets the default sort direction for $v$ in a way that function \code{cmp()} will be used to
  compare the entries of $v$.
\end{fcode}


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

\STITLE{Sort Functions}

Class \code{sort_vector< T >} provides a sort function, which allows to sort a vector in various
ways.  There are three different prototypes for this sort routine that allow a variety of calls
of the functions.  Some of the parameters of function \code{sort()} can obtain default values if
they are not specified in a call.  These default values will be indicated by ''\DEF''.

It is possible to restrict the sort routine to a part of a vector by explicitly passing on the
starting and ending indices to this function.  Whenever these values are invalid, the \LEH will
be invoked.

\begin{fcode}{void}{$v$.sort}{char sort_dir = \DEF, int $l$ = \DEF, int $r$ = \DEF}
  sorts the elements $v[l], \dots, v[r]$ according to the direction \code{$v$.sort_dir}.  Any other
  element in $v$ will remain in its position.  The value of \code{$v$.sort_dir} has to be either one of
  the two constants \code{SORT_VECTOR_UP} or \code{SORT_VECTOR_DOWN}.  If it differs from these
  values, the \LEH will be invoked.  If no values for $l$ and $r$ are given, the entire vector
  will be sorted.  If \code{$v$.sort_dir} is not specified either, the default sort direction for $v$
  will be used.
\end{fcode}

\begin{fcode}{void}{$v$.sort}{CMP_FUNC cmp, int $l$ = \DEF, int $r$ = \DEF}
  sorts the elements $v[l], \dots, v[r]$ according to the compare function \code{(*cmp)()}.  Any
  other element in $v$ will remain in its position.  The function \code{(*cmp)()} must be of
  correct type \code{CMP_FUNC}.  If no values for $l$ and $r$ are given, the entire vector will
  be sorted.
\end{fcode}

\begin{fcode}{void}{$v$.sort}{int $l$, int $r$}
  sorts the elements $v[l], \dots, v[r]$ according to the default sort direction of $v$.
\end{fcode}


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

\STITLE{Search Functions}

As a second feature the class \code{sort_vector< T >} provides functions for linear and binary
search in a vector.

\begin{cfcode}{bool}{$v$.linear_search}{const T & $x$, int & $\mathit{pos}$}
  searches $x$ in vector $v$.  If $x$ can be found, this function will return \TRUE and
  $\mathit{pos}$ will hold the index of its first occurence in $v$.  Otherwise, the return value
  will be \FALSE.
\end{cfcode}

The function \code{bin_search()} searches for an element $x$ in a vector using a binary search
strategy.  (Beware of the fact, that this routine can work successfully only if the elements of
the vector are sorted in an appropriate way.) Its return value will be \TRUE if it succeeds, and
\FALSE otherwise.  If $x$ can be found in a vector, $\mathit{pos}$ will hold the index of its
\emph{first} occurence or else, $\mathit{pos}$ will be the index, where $x$ can be inserted
according to the corresponding sort direction.

Some of the parameters of function \code{bin_search()} can obtain default values if they are not
specified in a call.  These default values will be indicated by ''\DEF''.

It is possible to restrict the search to a part of a vector by explicitly passing on the
starting and ending indices to this function.  Whenever these values are invalid, the \LEH will
be invoked.

\begin{cfcode}{bool}{$v$.bin_search}{const T & $x$, int & $\mathit{pos}$, char sort_dir = \DEF,
    int $l$ = \DEF, int $r$ = \DEF}%
  searches for $x$ among the elements $v[l], \dots, v[r]$ using the sort direction
  \code{$v$.sort_dir}.  Its value must be either of the two constants \code{SORT_VECTOR_UP} or
  \code{SORT_VECTOR_DOWN}.  If \code{$v$.sort_dir} differs from these values, the \LEH will be
  invoked.  If no values for $l$ and $r$ are given, the search will be carried out on the entire
  vector.  If \code{$v$.sort_dir} is not specified either, the default sort-direction for $v$
  will be used.
\end{cfcode}

\begin{cfcode}{bool}{$v$.bin_search}{const T & $x$, int & $\mathit{pos}$, CMP_FUNC cmp, int $l$ = \DEF, int $r$ = \DEF}
  searches for $x$ among the elements $v[l], \dots, v[r]$ using function \code{(*cmp)()} to
  compare these entries.  The function \code{(*cmp)()} must be of correct type \code{CMP_FUNC}.
  If no values for $l$ and $r$ are given, the search will be carried out on the entire vector.
  If \code{$v$.sort_dir} is not specified either, the default sort direction for $v$ will be
  used.
\end{cfcode}

\begin{cfcode}{bool}{$v$.bin_search}{const T & $x$, int & $\mathit{pos}$, int $l$, int $r$}
  searches for $x$ among the elements $v[l], \dots, v[r]$ using the default sort direction of $v$.
\end{cfcode}


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

\STITLE{Insert Functions}

The class \code{sort_vector< T >} also supports several functions to insert a new element into a
vector.  These use the member function \code{$v$.set_size()} to extend the size of a vector $v$ by
1.  If this cannot successfully be done, the vector will be left unchanged.  In that case, the
\LEH will be invoked.

An element $x$ can either be inserted at a specified position (using the function
\code{insert_at()} of class \code{base_vector< T >}) or it can also be automatically inserted at
its \emph{correct} position according to the vector's sort direction.

The function \code{insert()} provides several prototypes that allow to optionally specify a sort
direction or a part of the vector in a call to it.  If these parameters are missing, $insert()$
will refer to the vector default sort direction or consider the entire vector, respectively.

Note, that a vector must have been sorted before using the function \code{insert()}.  The sort
direction used in the sort procedure must correspond to the one specified here.

\begin{fcode}{void}{$v$.insert}{const T & $x$, char sort_dir = \DEF, int $l$ = \DEF, int $r$ = \DEF}
  uses the function \code{bin_search()} to determine the correct position of $x$ in $v$
  according to the specified sort direction.  If $l$ and $r$ are specified, the search for $x$
  will be restricted to the part $v[l], \dots, v[r]$.  After $x$ is inserted at the corresponding
  position, every succeeding element in $v$ will be moved one place to the right.  The value of
  \code{$v$.sort_dir} must be either one of the two constants \code{SORT_VECTOR_UP} or
  \code{SORT_VECTOR_DOWN}.  If \code{$v$.sort_dir} differs from these values, the \LEH will be
  invoked.
  
  If no values are given for $l$, $r$ or \code{sort_dir}, the default values will be passed on
  to the function \code{bin_search()}, i.e. the search for $x$ will be carried out on the entire
  vector and according to its default sort direction.
\end{fcode}

\begin{fcode}{void}{$v$.insert}{const T & $x$, CMP_FUNC cmp, int $l$ = \DEF, int $r$ = \DEF}
  uses the function \code{bin_search()} to determine the correct position of $x$ in $v$
  according to the compare function \code{(*cmp)()}.  If $l$ and $r$ are specified, the search
  for $x$ will be restricted to the part $v[l], \dots, v[r]$.  After $x$ is inserted at the
  corresponding position, every succeeding element in $v$ will be moved one place to the right.
  
  If no values are given for $l$ and $r$, the default values will be passed on to the function
  \code{bin_search()}, i.e. the search for $x$ will be carried out on the entire vector.
\end{fcode}

\begin{fcode}{void}{$v$.insert}{const T & $x$, int $l$, int $r$}
  uses the function \code{bin_search()} to determine the correct position of $x$ in $v$
  according to the default sort direction of $v$.  The search for $x$ will be restricted to the
  part $v[l], \dots, v[r]$.  After $x$ is inserted at the corresponding position, every succeeding
  element in $v$ will be moved one place to the right.
\end{fcode}


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

\STITLE{Remove Functions}

Furthermore, the class \code{sort_vector< T >} supports functions to remove elements from a
vector.  These functions use \code{$v$.set_size()} to deminish the size of the vector after the
removal.

The function \code{remove()} initiates \code{bin_search()} first to find a given element $x$ in
a vector.  If this search was successfully done, $one$ occurrence of $x$ will be removed from
$v$.  Any element in $v$ succeeding $x$ will be moved one position to the left and the size of
the vector will be diminished by 1.  If $x$ cannot be found in the vector, $v$ will be left
unchanged and the return value will be \FALSE.

The function \code{remove()} also provides several prototypes that allow to optionally specify a
sort direction or a part of the vector.  If these parameters are missing, \code{remove()} will
refer to the vector default sort direction and consider the entire vector, respectively.

\begin{fcode}{bool}{$v$.remove}{const T & $x$, char sort_dir = \DEF, int $l$ = \DEF, int $r$ = \DEF}
  uses the function \code{bin_search()} to find $x$ in $v$ using the specified sort direction.
  If $l$ and $r$ are specified, the search for $x$ will be restricted to the part
  $v[l], \dots, v[r]$.  If $x$ can be found in the vector, its first occurence will be deleted.
  The value of \code{$v$.sort_dir} must be one either of the two constants \code{SORT_VECTOR_UP}
  or \code{SORT_VECTOR_DOWN}.  If \code{$v$.sort_dir} differs from these values, the \LEH will be
  invoked.
  
  If no values are given for $l$, $r$ or \code{$v$.sort_dir}, the default values will be passed on
  to the function \code{bin_search()}, i.e. the search for $x$ will be carried out on the entire
  vector and according to its default sort direction.
\end{fcode}

\begin{fcode}{bool}{$v$.remove}{const T & $x$, CMP_FUNC cmp, int $l$ = \DEF, int $r$ = \DEF}
  uses the function \code{$v$.bin_search()} to find $x$ in $v$ using the compare function
  \code{(*cmp)()}.  If $l$ and $r$ are specified, the search for $x$ will be restricted to the
  part $v[l], \dots, v[r]$.  If $x$ can be found in the vector, its first occurence will be
  deleted.
  
  If no values are given for $l$ and $r$, the default values will be passed on to the function
  \code{bin_search()}, i.e. the search for $x$ will be carried out on the entire vector.
\end{fcode}

\begin{fcode}{bool}{$v$.remove}{const T & $x$, int $l$, int $r$}
  uses the function \code{bin_search()} to find $x$ in $v$ using the default sort-direction of
  $v$.  The search for $x$ will be restricted to the part $v[l], \dots, v[r]$.  If $x$ can be
  found in the vector, its first occurence will be deleted.
\end{fcode}


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

\SEEALSO

\SEE{base_vector}, \SEE{file_vector},
\SEE{math_vector}


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

\NOTES

As described in the template introduction (see page \pageref{template_introduction}) for using
an instance of type \code{sort_vector< T >} the type $T$ has to have at least
\begin{itemize}
\item a swap function \code{void swap(T &, T&)},
\item the input operator \code{>>},
\item the output operator \code{<<},
\item the assignment operator \code{=} and
\item the compare operators \code{<} and \code{>}.
\end{itemize}


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

\EXAMPLES

\begin{quote}
\begin{verbatim}
#include <LiDIA/sort_vector.h>

int main()
{
    sort_vector < double > w ;

    cout << " w = " ;
    cin >> w ;

    w.sort();

    cout << w << flush;
}
\end{verbatim}
\end{quote}

For further examples please refer to \path{LiDIA/src/templates/vector/vector_appl.cc}


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

\AUTHOR

Frank Lehmann, Markus Maurer, Stefan Neis, Thomas Papanikolaou, Patrick
Theobald
