source: trunk/doc/concepts.doxygen

// $Id: concepts.doxygen 3579 2017-01-16 03:54:43Z peter $
//
// Copyright (C) 2008 Jari Häkkinen, Peter Johansson, Markus Ringnér
// Copyright (C) 2009, 2010, 2011, 2014, 2017 Peter Johansson
//
// This file is part of the yat library, http://dev.thep.lu.se/yat
//
// The yat library is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; either version 3 of the
// License, or (at your option) any later version.
//
// The yat library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with yat. If not, see <http://www.gnu.org/licenses/>.


/**
\page Concepts Concepts

This page lists all the C++ concepts in the yat project.

- \subpage concept_container_2d
- \subpage concept_data_iterator
- \subpage concept_distance
- \subpage concept_mutable_container_2d
- \subpage concept_neighbor_weighting
- \subpage concept_weighted_iterator
*/


/**
\page concept_container_2d Container2D

\section concept_container_2d_description Description

\ref concept_container_2d is a <a
href="http://www.sgi.com/tech/stl/Container.html">Container</a> that
stores elements in a two-dimensional array (columns and rows). It
provides element access of a specific row and column, as well
as iterators that can be used to iterate over a specific column or
row.

\section concept_container_2d_requirments Requirements

A \ref concept_container_2d provides the following:

\subsection concept_container_2d_types Types

<table cellspacing=0 border=1>
<tr><td>Value type</td><td><tt>X::value_type</tt></td>
<td>Type of element stored in Container.</td>
</tr>
<tr><td>Const reference type</td><td><tt>X::const_reference</tt></td>
<td>A type that behaves as const reference to the \ref
concept_container_2d 's value type.</td>
</tr>
<tr>
<td>Const iterator type</td>
<td><tt>X::const_iterator</tt></td>
<td>
A read-only iterator that can be used to iterate over the entire \ref
concept_container_2d. Typically the iterator iterates along a
row, and when the end of one row is reached it jumps to the
beginning of the next row.
</td>
</tr>
<tr>
<td>Const column iterator type</td>
<td><tt>X::const_column_iterator</tt></td>
<td>
A read-only iterator that can be used to examine the elements in one
column of the \ref concept_container_2d.
</td>
</tr>
<tr>
<td>Const row iterator type</td>
<td><tt>X::const_row_iterator</tt></td>
<td>
A read-only iterator that can be used to examine the elements in one
row of the \ref concept_container_2d.
</td>
</tr>
</table>

\subsection concept_container_2d_public_functions Public Functions

<table cellspacing=0 border=1>
<tr>
<th>Name</th><th>Expression</th><th>Precondition</th><th>Return type</th>
<th>Postcondition</th>
</tr>
<tr>
<td>Beginning of range</td>
<td><tt>a.begin()</tt></td>
<td>&nbsp;</td>
<td><tt>const_iterator</tt></td>
<td>&nbsp;</td>
</tr>
<tr>
<td>Beginning of column</td>
<td><tt>a.begin_column(size_t column)</tt></td>
<td><tt>0 &lt;= column &lt; a.columns()</tt></td>
<td><tt>const_column_iterator</tt></td>
<td>&nbsp;</td>
</tr>
<tr>
<td>Beginning of row</td>
<td><tt>a.begin_row(size_t row)</tt></td>
<td><tt>0 &lt;= row &lt; a.rows()</tt></td>
<td><tt>const_row_iterator</tt></td>
<td>&nbsp;</td>
</tr>
<tr>
<td>End of range</td>
<td><tt>a.end()</tt></td>
<td>&nbsp;</td>
<td><tt>const_iterator</tt></td>
<td>&nbsp;</td>
</tr>
<tr>
<td>End of column</td>
<td><tt>a.end_column(size_t column)</tt></td>
<td><tt>0 &lt;= column &lt; a.columns()</tt></td>
<td><tt>const_column_iterator</tt></td>
<td>&nbsp;</td>
</tr>
<tr>
<td>End of row</td>
<td><tt>a.end_row(size_t row)</tt></td>
<td><tt>0 &lt;= row &lt; a.rows()</tt></td>
<td><tt>const_row_iterator</tt></td>
<td>&nbsp;</td>
</tr>
<tr>
<td>Columns</td>
<td><tt>a.columns()</tt></td>
<td>&nbsp;</td>
<td><tt>size_t</tt></td>
<td>&nbsp;</td>
</tr>
<tr>
<td>Rows</td>
<td><tt>a.rows()</tt></td>
<td>&nbsp;</td>
<td><tt>size_t</tt></td>
<td>&nbsp;</td>
</tr>
<tr>
<td>Element Access</td>
<td><tt>a(size_t row, size_t column)</tt></td>
<td><tt>0 &lt;= row &lt; a.rows()</tt> and
<tt>0 &lt;= column &lt; a.columns()</tt></td>
<td><tt>const_reference</tt></td>
<td>&nbsp;</td>
</tr>
</table>

\section concept_container_2d_implementations Implementations

Examples of concept \ref concept_container_2d include:
  - theplu::yat::classifier::MatrixLookup,
  - theplu::yat::classifier::MatrixLookupWeighted
  - theplu::yat::classifier::KernelLookup.

*/

/**
\page concept_mutable_container_2d Mutable Container2D

\section concept_mutable_container_2d_description Description

\ref concept_mutable_container_2d is a \ref concept_container_2d that
also provides non-const access to its elements.

\section concept_mutable_container_2d_requirments Requirements

In addition to the requirements defined in \ref concept_container_2d,
a \ref concept_mutable_container_2d also provides the following:

\subsection concept_mutable_container_2d_types Types

<table cellspacing=0 border=1>
<tr><td>Reference type</td><td><tt>X::reference</tt></td>
<td>A type that behaves as reference to the \ref
concept_mutable_container_2d 's value type.</td>
</tr>
<tr>
<td>Iterator type</td>
<td><tt>X::iterator</tt></td>
<td>

A mutable iterator similar to Const iterator type, which can be used to
iterate over the \ref concept_mutable_container_2d (and modify the
elements). Typically the iterator iterates along a row, and when the
end of one row is reached it jumps to the beginning of the next row.

</td>
</tr>
<tr>
<td>Column iterator type</td>
<td><tt>X::column_iterator</tt></td>
<td>
A mutable iterator that can be used to modify the elements in one
column of the \ref concept_mutable_container_2d.
</td>
</tr>
<tr>
<td>Row iterator type</td>
<td><tt>X::row_iterator</tt></td>
<td>
A mutable iterator that can be used to modify the elements in one
row of the \ref concept_mutable_container_2d.
</td>
</tr>
</table>

\subsection concept_mutable_container_2d_public_functions Public Functions

<table cellspacing=0 border=1>
<tr>
<th>Name</th><th>Expression</th><th>Precondition</th><th>Return type</th>
<th>Postcondition</th>
</tr>
<tr>
<td>Beginning of range</td>
<td><tt>a.begin()</tt></td>
<td>&nbsp;</td>
<td><tt>iterator</tt></td>
<td><tt>iterator</tt> is derefenceable, unless <tt>a</tt> is empty</td>
</tr>
<tr>
<td>Beginning of column</td>
<td><tt>a.begin_column(size_t column)</tt></td>
<td><tt>0 &lt;= column &lt; a.columns()</tt></td>
<td><tt>column_iterator</tt></td>
<td><tt>column_iterator</tt> is derefenceable, unless <tt>a</tt> is empty</td>
</tr>
<tr>
<td>Beginning of row</td>
<td><tt>a.begin_row(size_t row)</tt></td>
<td><tt>0 &lt;= row &lt; a.rows()</tt></td>
<td><tt>row_iterator</tt></td>
<td><tt>row_iterator</tt> is derefenceable, unless <tt>a</tt> is empty</td>
</tr>
<tr>
<td>End of range</td>
<td><tt>a.end()</tt></td>
<td>&nbsp;</td>
<td><tt>iterator</tt></td>
<td>&nbsp;</td>
</tr>
<tr>
<td>End of column</td>
<td><tt>a.end_column(size_t column)</tt></td>
<td><tt>column&lt;a.columns()</tt></td>
<td><tt>column_iterator</tt></td>
<td>&nbsp;</td>
</tr>
<tr>
<td>End of row</td>
<td><tt>a.end_row(size_t row)</tt></td>
<td><tt>row&lt;a.rows()</tt></td>
<td><tt>row_iterator</tt></td>
<td>&nbsp;</td>
</tr>
<tr>
<td>Element Access</td>
<td><tt>a(size_t row, size_t column)</tt></td>
<td><tt>0 &lt;= row &lt; a.rows()</tt> and
<tt>0 &lt;= column &lt; a.columns()</tt></td>
<td><tt>reference</tt></td>
<td>&nbsp;</td>
</tr>
</table>

\section concept_mutable_container_2d_implementations Implementations

Examples of concept \ref concept_mutable_container_2d include:
  - theplu::yat::utility::Matrix,
  - theplu::yat::utility::MatrixWeighted

*/

/**
\page concept_distance Distance

\section concept_distance_description Description

\ref concept_distance is a concept for classes implementing different
alternatives to calculate the distance between two ranges. For details
on requirements needed for a class modelling the concept \ref
concept_distance refer to section below, but a convenient way to
implement a class is to use class theplu::yat::statistics::Distance as
base class.

\section concept_distance_requirments Requirements

Classes modelling the concept \ref concept_distance should have a copy
constructor

\verbatim
Distance(const Distance& d);
\endverbatim

and also implement the following public function:

\verbatim
template<typename Iterator1, typename Iterator2>
double  operator() (Iterator1 beg1, Iterator1 end1, Iterator2 beg2) const
\endverbatim

This function should calculate and return the distance between
elements of two ranges. The first range is given by [\a beg1, \a end1)
and the second range starts with \a beg2 and has the same length as
the first range. The function should support iterators that model \ref
concept_data_iterator and \forward_traversal_iterator, in other words,
the function should not assume any functionality not guaranteed by
concepts \forward_traversal_iterator and \readable_iterator.

As \ref concept_data_iterator should be supported, class
should support \ref concept_weighted_iterator. Typically a \ref
concept_distance class has a fast calculation for the case when
neither of the two input ranges is weighted, and a separate function
taking care of weights. A convenient way to select between unweighted and
weighted implementations is to utilize tag structs
theplu::yat::utility::unweighted_iterator_tag and
theplu::yat::utility::weighted_iterator_tag as returned from meta-function
theplu::yat::utility::weighted_if_any2.

The class theplu::yat::utility::DistanceConcept an be used to test
that a class fulfills these requirements.

\section concept_distance_implementations Implementations

Examples of classes modelling the concept \ref concept_distance
include theplu::yat::statistics::PearsonDistance and
theplu::yat::statistics::EuclideanDistance.

\see \ref weighted_distance

*/

/**
\page concept_neighbor_weighting Neighbor Weighting Method

\section concept_neighbor_weighting_description Description

\ref concept_neighbor_weighting is a concept used in connection with
theplu::yat::classifier::KNN - classes used as the template argument
NeighborWeighting should implement this concept.

\section concept_neighbor_weighting_requirements Requirements

Classes modelling the concept \ref concept_neighbor_weighting should
be DefaultConstructible and Assignable as well as
implement the following public function:

\verbatim
void operator()(const utility::VectorBase& distance,
                const std::vector<size_t>& k_sorted,
                const Target& target,
                utility::VectorMutable& prediction) const
\endverbatim

For a test sample, this function should calculate a total vote
(i.e. based on all k nearest neighbors) for each class. The vector \a
distance contains the distances from a test sample to all training
samples. The vector \a k_sorted contains the indices (for both \a
distance and \a target) to the k training samples with the smallest
distances to the test sample. The class for each training sample is
given by \a target, which is sorted in the same sample order as \a
distance. For each class the function calculates a total vote based on
the the nearest neighbors of the test sample that belong to the
class. The total vote for each class is stored in the vector \a
prediction.  The function should be implemented such that nearest
neighbors with distance infinity do not vote.

\section concept_neighbor_weighting_implementations Implementations

Examples of classes modelling the concept \ref
concept_neighbor_weighting include
theplu::yat::classifier::KNN_Uniform,
theplu::yat::classifier::KNN_ReciprocalDistance and
theplu::yat::classifier::KNN_ReciprocalRank.

*/

/**
\page concept_weighted_iterator Weighted Iterator

\section concept_weighted_iterator_description Description

Most functionality in yat come in two versions: one optimized for
speed and one weighted version allowing for missing value (see \ref
weighted_statistics). For example, weighted containers such as
theplu::yat::utility::MatrixWeighted and
theplu::yat::classifier::MatrixLookupWeighted allow an easy way to
handle missing values. Iterators that iterate over such weighted
containers are by definition \ref concept_weighted_iterator. This
concept is orthogonal against other iterator concepts such as Random
Access Iterator.

\section concept_weighted_iterator_requirements Requirements

When implementing a new iterator that may be a \ref
concept_weighted_iterator, there are a few things to concider.

\subsection weighted_iterator_traits

To decide whether an iterator is weighted, there exists a
meta-function
theplu::yat::utility::weighted_iterator_traits<Iterator>::type that
will return either theplu::yat::utility::weighted_iterator_tag or
theplu::yat::utility::unweighted_iterator_tag. The default
implementation of this meta-function works in most cases, including on
all std::iterators, but if you implement a new iterator make sure it
behaves as you desire, or you need to create a specialization.

\subsection iterator_traits

Sometimes it is useful to have unweighted iterators behaving as though
they were weighted. For instance,
theplu::yat::statistics::EuclideanDistance calculates the distance
between two ranges. If both ranges are unweighted the unweighted
version is used, and when any of the two ranges is weighted the
weighted version kicks in. In order to make this work also when
comparing weighted and unweighted ranges, there must a mechanism to
let the unweighted iterator behave as though it were weighted.

This can be accomplished through
theplu::yat::utility::iterator_traits, which enables access to data
value as well as to weight value. For unweighted iterators the weight
value is always equal to 1.0 and is not mutable. The default
implementation works for most iterators including all unweighted, but
if you implement a new weighted iterator you need to check that the
default implementation will work for you (see class
documentation). Otherwise, you will need to implement a
specialization. Note that the default implementation requires that, if
\c iterator is a weighted iterator, its \c reference must have
member functions data() and weight(). This should not be a problem as
long as \c reference is theplu::yat::utility::DataWeight or
theplu::yat::utility::DataWeightProxy, but could potentially be a
problem when creating weighted iterators with other \c reference.

*/

/**
\page concept_data_iterator Data Iterator

\section concept_data_iterator_description Description

\ref concept_data_iterator is an iterator that is either:

  - a \ref concept_weighted_iterator with value type convertible to
theplu::yat::utility::DataWeight.
  - an unweighted iterator with value type convertible to \c double.

in addition

  - \c theplu::yat::utility::weighted_iterator_traits<I> must work
    well, which implies that iterator, \c I is a \readable_iterator
    and \single_pass_iterator.

\section concept_data_iterator_implementations Implementations

Examples of concept \ref concept_data_iterator include:
  - theplu::yat::utility::Matrix::iterator,
  - theplu::yat::utility::MatrixWeighted::iterator,
  - theplu::yat::classifier::MatrixLookup::const_iterator,
  - theplu::yat::classifier::MatrixLookupWeighted::const_iterator
*/