%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%  base_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
%%

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

\NAME

\CLASS{base_vector < T >} \dotfill parameterized base vector class


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

\ABSTRACT

The class \code{base_vector< T >} realizes the concept of a vector as a more advanced array
\begin{displaymath}
  v = (v_i) \in T^m \enspace,\quad 0 \leq i < m \enspace.
\end{displaymath}
It allows to create vectors and offers elementary access functions.  \code{T} is allowed to be
either a built-in type or a class.


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

\DESCRIPTION

A variable $v$ of type \code{base_vector< T >} consists of a 1-dimensional array \code{T *
  data}, an unsigned integer \code{mode}, a float \code{expansion_ratio} as well as two integers
\code{size} and \code{capacity} which describe the length of the vector.  We call the number of
allocated elements the capacity of $v$.  The size of the vector is the number of items actually
used in $v$.  Thus, this value will never decrease; neither will it exceed the capacity.

Both values can individually be changed for a vector $v$ by using the functions
\code{$v$.set_capacity()} and \code{$v$.set_size()}, respectively.

As an example, the declaration
\begin{quote}
  \code{base_vector < int > v(10,0)}
\end{quote}
will create a \code{base_vector< int >} with 10 elements allocated, so $\code{$v$.capacity} =
10$ and $\code{$v$.size} = 0$.  If we use the first $s$ elements of $v$ only, $s$ will be the
size of $v$.  In our example, after the declaration, $v$ has $\code{$v$.size} = 0$ and if we
assign
\begin{displaymath}
 v[0] = 1 \enspace,\quad v[1] = 2
\end{displaymath}
we obtain $\code{$v$.size} = 2$.  As shown in this example the first element of $v$ has index 0
and the last one has index $\code{$v$.size} - 1$.

Furthermore, a \code{base_vector} $v$ can be of either fixed or expanding size.  For so called
fixed vectors one can only change the number of allocated items in the vector by using the
member function \code{$v$.set_capacity()}.  I.e. neither is it possible to access the vector at an
index which is greater than the vector's capacity, nor may function \code{$v$.set_size()} be
called with a size greater than this value.

Vectors of expanding size automatically allocate memory if access is required for an index
greater than its current capacity or the number of items by using the member function
\code{$v$.set_size()} exceeds that value.  The new amount of memory to be allocated in these cases
will then be computed using the expansion ratio of the vector.  This is a factor by which the
required number of elements will be multiplied before actually reallocating memory.  The value
of this factor for a vector $v$ is $2.0$ by default and may be altered at any time using the
member function \code{$v$.set_exp_ratio()}.  The expansion ratio has to be at least $1.0$.

The property, whether a vector is of fixed or expanding size, is stored in a member called \code{mode}.
The value of this member can be either of the constants \code{FIXED} or \code{EXPAND}.  By
default, each vector is of fixed size.  Its mode can explicitly be set by either using the
function \code{v.set_mode()} or by adding \code{FIXED} or \code{EXPAND} as an additional
argument to the corresponding constructor.

In the following descriptions we use \code{$v$.size} to label the size and \code{$v$.capacity}
to label the capacity of vector $v$.


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

\CONS

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

\begin{fcode}{ct}{base_vector< T >}{lidia_size_t $c$, char $\mathit{mode}$}
  constructs a vector with capacity $c$ initialized with values generated by the default
  constructor for type \code{T}.  $\mathit{mode}$ can be either \code{FIXED} or \code{EXPAND}.
\end{fcode}

\begin{fcode}{ct}{base_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}{base_vector< T >}{lidia_size_t $c$, lidia_size_t $s$, char $\mathit{mode}$}
  constructs a vector with capacity $c$ and size $s$ initialized with values generated by the
  default constructor for type \code{T}.  $\mathit{mode}$ can be either \code{FIXED} or
  \code{EXPAND}.
\end{fcode}

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

\begin{fcode}{ct}{base_vector< T >}{const base_vector< T > & $w$, char $\mathit{mode}$}
  constructs a vector with capacity \code{$w$.size} initialized with the elements of $w$.
  $\mathit{mode}$ can be either \code{FIXED} or \code{EXPAND}.
\end{fcode}

\begin{fcode}{ct}{base_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$.  If the array $a$ has less than $l$ elements the \LEH will be invoked.
\end{fcode}

\begin{fcode}{ct}{base_vector< T >}{const T * $a$, lidia_size_t $l$, char $\mathit{mode}$}
  constructs a vector with capacity $l$ and size $l$ initialized with the first $l$ elements of
  the array $a$.  If the array $a$ has less than $l$ elements the \LEH will be invoked.
  $\mathit{mode}$ can be either \code{FIXED} or \code{EXPAND}.
\end{fcode}

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


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

\ACCS

Let $v$ be of type \code{base_vector< T >}.  Note, that we start the numbering of elements of a
\code{base_vector< T >} with zero.


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

\SSTITLE{Access to the size}

\begin{cfcode}{lidia_size_t}{v.size}{}
  returns the size of $v$.
\end{cfcode}

\begin{cfcode}{lidia_size_t}{v.get_size}{}
  returns the size of $v$.
\end{cfcode}

\begin{fcode}{void}{v.set_size}{lidia_size_t $s$}
  sets the size of $v$ to $s$ if the capacity of $v$ is large enough.  If $s$ exceeds
  \code{$v$.capacity} and $v$ is of expanding size, new memory will be allocated by using the
  function \code{$v$.set_capacity()}.  The number of elements allocated in that case is $s \cdot
  \code{$v$.exp_ratio}$.  If these actions can not successfully be performed, the \LEH will be
  invoked.
\end{fcode}


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

\SSTITLE{Access to the capacity}

\begin{cfcode}{lidia_size_t}{$v$.capacity}{}
  returns the capacity of $v$.
\end{cfcode}

\begin{cfcode}{lidia_size_t}{$v$.get_capacity}{}
  returns the capacity of $v$.
\end{cfcode}

\begin{fcode}{void}{$v$.set_capacity}{lidia_size_t $c$}
  sets the capacity of $v$ to $c$ by allocating exactly $c$ elements for $v$.  Here, $c$ must be
  a positive value.  If $c$ is $0$, the elements of $v$ will be deleted.  If an error occurs in
  this function, the \LEH will be invoked.
\end{fcode}

\begin{fcode}{void}{$v$.reset}{}
  deallocates the vector elements and sets \code{$v$.capacity} and \code{$v$.size} to zero.
\end{fcode}

\begin{fcode}{void}{$v$.kill}{}
  deallocates the vector elements and sets \code{$v$.capacity} and \code{$v$.size} to zero.
\end{fcode}


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

\SSTITLE{Access to the \textcode{exp\_ratio}}

\begin{cfcode}{float}{$v$.exp_ratio}{}
  returns the expansion ratio of $v$.
\end{cfcode}

\begin{cfcode}{float}{$v$.get_exp_ratio}{}
  returns the expansion ratio of $v$.
\end{cfcode}

\begin{fcode}{void}{$v$.set_exp_ratio}{float $e$}
  sets the expansion ratio of $v$ to $e$.  The value of $e$ must be at least $1.0$.  If $e$ is
  invalid, the expansion ratio of $v$ will be set to $1.0$.
\end{fcode}


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

\SSTITLE{Access to the mode}

\begin{cfcode}{char}{$v$.get_mode}{}
  returns the mode of $v$.
\end{cfcode}

\begin{fcode}{void}{$v$.set_mode}{char $\mathit{mode}$}
  sets mode of $v$ to $\mathit{mode}$ which must be either of the two constants \code{FIXED} or
  \code{EXPAND}.  If $\mathit{mode}$ differs from these values, the mode of $v$ will be set to
  \code{FIXED}.
\end{fcode}


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

\SSTITLE{Access to an element}

\begin{fcode}{T &}{operator[]}{lidia_size_t $i$}
  If the mode of $v$ is \code{FIXED}, the operator returns a reference to the $(i+1)$-st element
  in $v$, provided that $i$ is less than the capacity of the vector.  If $i$ is too large, the
  \LEH will be invoked.  The size of the vector will be set appropriately after a successful
  access (i.e.  it will be set to $i+1$ if this value is greater than the previous size).
  
  If $v$ is of expanding size, the capacity of the vector will be extended if $i$ is not less
  than its current value.  This is done by a call of the function \code{$v$.set_capacity()}.
  The number of elements that will be allocated is $(i+1) \cdot \code{$v$.exp_ratio}$.  Provided
  that the memory reallocation succeeds, the operator will return a reference to the $(i+1)$-st
  element in $v$.  The size of the vector will be set appropriately.
\end{fcode}

\begin{cfcode}{const T &}{operator[]}{lidia_size_t $i$}
  returns a constant reference to the $(i+1)$-st element in $v$ where $i$ has to be non-negative
  and less than \code{$v$.size}.  Otherwise the \LEH will be invoked.
\end{cfcode}

\begin{cfcode}{const T &}{member}{lidia_size_t $i$}
  returns a constant reference to the $(i+1)$-st element in $v$ where $i$ has to be non-negative
  and less than \code{$v$.size}.  Otherwise the \LEH will be invoked.
\end{cfcode}


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

\SSTITLE{Access to the array of datas}

\begin{fcode}{void}{$v$.set_data}{const T * $d$, lidia_size_t $l$)}
  copies $l$ elements $d[0], \dots, d[l-1]$ to vector $v$ and adjusts its capacity.  If array $d$
  has less than $l$ elements the behaviour of this function is undefined.
\end{fcode}

\begin{cfcode}{T *}{$v$.get_data}{}
  returns a pointer to a copy of the vector elements.
\end{cfcode}


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

\ASGN

Let $v$ be of type \code{base_vector< T >}.  The operator \code{=} is overloaded.  For efficiency
reasons the following functions are also implemented:

\begin{fcode}{void}{assign}{base_vector< T > & $v$, const base_vector< T > & $w$}
  allocates \code{$w$.size} elements for $v$ using \code{$v$.set_capacity()} and copies the entries of
  $w$ into $v$.
\end{fcode}

\begin{fcode}{void}{v.assign}{lidia_size_t $\mathit{at}$, const base_vector< T > & $w$,
    lidia_size_t $\mathit{from}$, lidia_size_t $\mathit{to}$}%
  copies the elements $w[\mathit{from}], \dots, w[\mathit{to}]$ to vector $v$, starting at
  position $v[\mathit{at}]$.  The corresponding elements of $v$ will be overwritten.  The size
  of $v$ will be adjusted appropriately.
\end{fcode}

\begin{fcode}{void}{$v$.fill}{const T & $x$}
  $v[i] \assign x$, $0 \leq i < \code{$v$.size()}$.
\end{fcode}


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

\STITLE{Reverse Functions}

\begin{fcode}{void}{$v$.reverse}{}
  rearranges the elements of vector $v$ in reverse order.
\end{fcode}

\begin{fcode}{void}{$v$.reverse}{const base_vector< T > & $w$}
  copies the elements of $w$ in reverse order into vector $v$.  If $w$ does not alias $v$,
  \code{$w$.size} elements will be allocated for $v$ by using \code{$v$.set_capacity()}.
\end{fcode}


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

\STITLE{Swap Functions}

\begin{fcode}{void}{swap}{base_vector< T > & $v$, base_vector< T > & $w$}
  exchanges the complete information of $v$ and $w$.
\end{fcode}

%% \begin{fcode}{void}{v.swap}{base_vector< T > & $w$}%%exchanges the complete information of $v$ and $w$.
% \end{fcode}


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

\STITLE{Concatenation}

\begin{fcode}{void}{$v$.concat}{const base_vector< T > u, const base_vector< T > w}
  stores in $v$ the concatenation of $u$ and $w$.  The capacity of $v$ will be set to the sum of
  the sizes of the two vectors $u$ and $w$.
\end{fcode}


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

\STITLE{Shift Functions}

\begin{fcode}{void}{$v$.shift_left}{lidia_size_t $\mathit{pos}$, lidia_size_t $\mathit{num}$}
  moves the elements of $v$ $\mathit{num}$ positions to the left starting at $v[\mathit{pos}]$
  thus overwriting some preceeding entries.  The size of $v$ will be reduced by $\mathit{num}$
  using the function \code{$v$.set_size()}.  The value of $\mathit{num}$ may not exceed
  $\mathit{pos}$.
\end{fcode}

\begin{fcode}{void}{$v$.shift_right}{lidia_size_t $\mathit{pos}$, lidia_size_t $\mathit{num}$}
  copies the elements of $v$ $\mathit{num}$ positions to the right starting at $v[\mathit{pos}]$
  possibly overwriting some succeeding elements in $v$.  The size of $v$ will be increased by
  $\mathit{num}$ using the function \code{$v$.set_size()}.
\end{fcode}


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

\STITLE{Insert Functions}

\begin{fcode}{void}{$v$.insert_at}{const T & $x$, int $pos$}
  extends the size of vector $v$ by 1 using \code{$v$.set_size()}, moves the elements of $v$ one
  position to the right starting at $v[\mathit{pos}]$ and sets $v[\mathit{pos}] \assign x$.  If
  $\mathit{pos} < 0$ the \LEH will be invoked.
\end{fcode}


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

\STITLE{Remove Functions}

\begin{fcode}{void}{remove_from}{lidia_size_t $\mathit{pos}$, lidia_size_t $n$ = 1}
  removes $n$ elements from the vector $v$ starting at $v[\mathit{pos}]$.  Any element in $v$
  succeeding $v[\mathit{pos}]$ will be moved $n$ positions to the left.  After a successfull
  deletion, the size of vector $v$ will be diminshed by $n$ using \code{$v$.set_size()}.
\end{fcode}


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

\IO

The \code{istream} operator \code{>>} and the \code{ostream} operator \code{<<} are overloaded.
The \code{istream} operator \code{>>} reads vectors of the form ''$[ v_{0} \dots v_{n-1} ]$''
from an input stream.

The \code{ostream} operator \code{<<} outputs the vector in the above described format.


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

\SEEALSO

\SEE{file_vector}, \SEE{math_vector},
\SEE{sort_vector}


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

\NOTES

\begin{enumerate}
\item As described in the template introduction (see page \pageref{template_introduction}) for
  using an instance of type \code{base_vector< T >} the type \code{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{<<} and
  \item the assignment operator \code{=}.
  \end{itemize}
\item As usually in C++ the numbering of the elements in a \code{base_vector} starts with zero.
\end{enumerate}


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

\EXAMPLES

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

int main()
{
    base_vector < int > u, v, w ;

    cout << " u = " ;
    cin >> u ;

    cout << " v = " ;
    cin >> v ;

    w.concat(u,v);

    cout << w ;
}
\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
