// $Id: concepts.doxygen 2504 2011-06-29 19:26:47Z peter $ // // Copyright (C) 2008 Jari Häkkinen, Peter Johansson, Markus Ringnér // Copyright (C) 2009, 2010, 2011 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 . /** \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 Container 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
Value typeX::value_type Type of element stored in Container.
Const reference typeX::const_reference A type that behaves as const reference to the \ref concept_container_2d 's value type.
Const iterator type X::const_iterator 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.
Const column iterator type X::const_column_iterator A read-only iterator that can be used to examine the elements in one column of the \ref concept_container_2d.
Const row iterator type X::const_row_iterator A read-only iterator that can be used to examine the elements in one row of the \ref concept_container_2d.
\subsection public_functions Public Functions
NameExpressionPreconditionReturn type Postcondition
Beginning of range a.begin()   const_iterator  
Beginning of column a.begin_column(size_t column) 0 <= column < a.columns() const_column_iterator  
Beginning of row a.begin_row(size_t row) 0 <= row < a.rows() const_row_iterator  
End of range a.end()   const_iterator  
End of column a.end_column(size_t column) 0 <= column < a.columns() const_column_iterator  
End of row a.end_row(size_t row) 0 <= row < a.rows() const_row_iterator  
Columns a.columns()   size_t  
Rows a.rows()   size_t  
Element Access a(size_t row, size_t column) 0 <= row < a.rows() and 0 <= column < a.columns() const_reference  
\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
Reference typeX::reference A type that behaves as reference to the \ref concept_mutable_container_2d 's value type.
Iterator type X::iterator 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.
Column iterator type X::column_iterator A mutable iterator that can be used to modify the elements in one column of the \ref concept_mutable_container_2d.
Row iterator type X::row_iterator A mutable iterator that can be used to modify the elements in one row of the \ref concept_mutable_container_2d.
\subsection public_functions Public Functions
NameExpressionPreconditionReturn type Postcondition
Beginning of range a.begin()   iterator iterator is derefenceable, unless a is empty
Beginning of column a.begin_column(size_t column) 0 <= column < a.columns() column_iterator column_iterator is derefenceable, unless a is empty
Beginning of row a.begin_row(size_t row) 0 <= row < a.rows() row_iterator row_iterator is derefenceable, unless a is empty
End of range a.end()   iterator  
End of column a.end_column(size_t column) column<a.columns() column_iterator  
End of row a.end_row(size_t row) row<a.rows() row_iterator  
Element Access a(size_t row, size_t column) 0 <= row < a.rows() and 0 <= column < a.columns() reference  
\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 have a copy constructor \verbatim Distance(const Distance& d); \endverbatim and also implement the following public function: \verbatim template 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 be DefaultConstructible and Assignable as well as implement the following public function: \verbatim void operator()(const utility::VectorBase& distance, const std::vector& 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::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 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. \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 */