source: trunk/doc/concepts.doxygen @ 2299

// $Id: concepts.doxygen 2299 2010-07-12 15:38:46Z peter $
//
// Copyright (C) 2008 Jari Häkkinen, Peter Johansson, Markus Ringnér
// Copyright (C) 2009, 2010 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 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 Requirements

A \ref concept_container_2d provides the following:

\subsection 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 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 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 Description

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

\section Requirements

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

\subsection 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 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 Implementations

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

*/

/**
\page concept_distance Distance

\section Description

\ref concept_distance is a concept for classes implementing different
alternatives to calculate the distance between two points.

\section Requirements

Classes modelling the concept \ref concept_distance should implement
the following public function:

\verbatim
template<typename Iter1, typename Iter2>
double  operator() (Iter1 beg1, Iter1 end1, Iter2 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 of the category
std::forward_iterator. The function should provide both a fast
calculation for unweighted iterators and a calculation for weighted
iterators. The latter correspond to the case where elements in a range
have both a value and a weight. The selection between unweighted and
weighted implementations should utilize
theplu::yat::utility::unweighted_iterator_tag and 
theplu::yat::utility::weighted_iterator_tag. Moreover
theplu::yat::utility::weighted_if_any2 should be utilized to provide a
weighted implementation if any of the two ranges is weighted, and an
unweighted implementation when both ranges are unweighted.

\section 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 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 Requirements

Classes modelling the concept \ref concept_neighbor_weighting should
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 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 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 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, \c iterator::reference must have
member functions data() and weight(). This should not be a problem as
long as \c iterator::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 Description

\ref concept_data_iterator is an iterator that comes in two shapes: 

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

\section 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
*/