source: trunk/doc/concepts.doxygen @ 3579

Last change on this file since 3579 was 3579, checked in by Peter, 5 years ago

merge release 0.14 into trunk

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 15.1 KB
Line 
1// $Id: concepts.doxygen 3579 2017-01-16 03:54:43Z peter $
2//
3// Copyright (C) 2008 Jari Häkkinen, Peter Johansson, Markus Ringnér
4// Copyright (C) 2009, 2010, 2011, 2014, 2017 Peter Johansson
5//
6// This file is part of the yat library, http://dev.thep.lu.se/yat
7//
8// The yat library is free software; you can redistribute it and/or
9// modify it under the terms of the GNU General Public License as
10// published by the Free Software Foundation; either version 3 of the
11// License, or (at your option) any later version.
12//
13// The yat library is distributed in the hope that it will be useful,
14// but WITHOUT ANY WARRANTY; without even the implied warranty of
15// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16// General Public License for more details.
17//
18// You should have received a copy of the GNU General Public License
19// along with yat. If not, see <http://www.gnu.org/licenses/>.
20
21
22/**
23\page Concepts Concepts
24
25This page lists all the C++ concepts in the yat project.
26
27- \subpage concept_container_2d
28- \subpage concept_data_iterator
29- \subpage concept_distance
30- \subpage concept_mutable_container_2d
31- \subpage concept_neighbor_weighting
32- \subpage concept_weighted_iterator
33*/
34
35
36/**
37\page concept_container_2d Container2D
38
39\section concept_container_2d_description Description
40
41\ref concept_container_2d is a <a
42href="http://www.sgi.com/tech/stl/Container.html">Container</a> that
43stores elements in a two-dimensional array (columns and rows). It
44provides element access of a specific row and column, as well
45as iterators that can be used to iterate over a specific column or
46row.
47
48\section concept_container_2d_requirments Requirements
49
50A \ref concept_container_2d provides the following:
51
52\subsection concept_container_2d_types Types
53
54<table cellspacing=0 border=1>
55<tr><td>Value type</td><td><tt>X::value_type</tt></td>
56<td>Type of element stored in Container.</td>
57</tr>
58<tr><td>Const reference type</td><td><tt>X::const_reference</tt></td>
59<td>A type that behaves as const reference to the \ref
60concept_container_2d 's value type.</td>
61</tr>
62<tr>
63<td>Const iterator type</td>
64<td><tt>X::const_iterator</tt></td>
65<td>
66A read-only iterator that can be used to iterate over the entire \ref
67concept_container_2d. Typically the iterator iterates along a
68row, and when the end of one row is reached it jumps to the
69beginning of the next row.
70</td>
71</tr>
72<tr>
73<td>Const column iterator type</td>
74<td><tt>X::const_column_iterator</tt></td>
75<td>
76A read-only iterator that can be used to examine the elements in one
77column of the \ref concept_container_2d.
78</td>
79</tr>
80<tr>
81<td>Const row iterator type</td>
82<td><tt>X::const_row_iterator</tt></td>
83<td>
84A read-only iterator that can be used to examine the elements in one
85row of the \ref concept_container_2d.
86</td>
87</tr>
88</table>
89
90\subsection concept_container_2d_public_functions Public Functions
91
92<table cellspacing=0 border=1>
93<tr>
94<th>Name</th><th>Expression</th><th>Precondition</th><th>Return type</th>
95<th>Postcondition</th>
96</tr>
97<tr>
98<td>Beginning of range</td>
99<td><tt>a.begin()</tt></td>
100<td>&nbsp;</td>
101<td><tt>const_iterator</tt></td>
102<td>&nbsp;</td>
103</tr>
104<tr>
105<td>Beginning of column</td>
106<td><tt>a.begin_column(size_t column)</tt></td>
107<td><tt>0 &lt;= column &lt; a.columns()</tt></td>
108<td><tt>const_column_iterator</tt></td>
109<td>&nbsp;</td>
110</tr>
111<tr>
112<td>Beginning of row</td>
113<td><tt>a.begin_row(size_t row)</tt></td>
114<td><tt>0 &lt;= row &lt; a.rows()</tt></td>
115<td><tt>const_row_iterator</tt></td>
116<td>&nbsp;</td>
117</tr>
118<tr>
119<td>End of range</td>
120<td><tt>a.end()</tt></td>
121<td>&nbsp;</td>
122<td><tt>const_iterator</tt></td>
123<td>&nbsp;</td>
124</tr>
125<tr>
126<td>End of column</td>
127<td><tt>a.end_column(size_t column)</tt></td>
128<td><tt>0 &lt;= column &lt; a.columns()</tt></td>
129<td><tt>const_column_iterator</tt></td>
130<td>&nbsp;</td>
131</tr>
132<tr>
133<td>End of row</td>
134<td><tt>a.end_row(size_t row)</tt></td>
135<td><tt>0 &lt;= row &lt; a.rows()</tt></td>
136<td><tt>const_row_iterator</tt></td>
137<td>&nbsp;</td>
138</tr>
139<tr>
140<td>Columns</td>
141<td><tt>a.columns()</tt></td>
142<td>&nbsp;</td>
143<td><tt>size_t</tt></td>
144<td>&nbsp;</td>
145</tr>
146<tr>
147<td>Rows</td>
148<td><tt>a.rows()</tt></td>
149<td>&nbsp;</td>
150<td><tt>size_t</tt></td>
151<td>&nbsp;</td>
152</tr>
153<tr>
154<td>Element Access</td>
155<td><tt>a(size_t row, size_t column)</tt></td>
156<td><tt>0 &lt;= row &lt; a.rows()</tt> and
157<tt>0 &lt;= column &lt; a.columns()</tt></td>
158<td><tt>const_reference</tt></td>
159<td>&nbsp;</td>
160</tr>
161</table>
162
163\section concept_container_2d_implementations Implementations
164
165Examples of concept \ref concept_container_2d include:
166  - theplu::yat::classifier::MatrixLookup,
167  - theplu::yat::classifier::MatrixLookupWeighted
168  - theplu::yat::classifier::KernelLookup.
169
170*/
171
172/**
173\page concept_mutable_container_2d Mutable Container2D
174
175\section concept_mutable_container_2d_description Description
176
177\ref concept_mutable_container_2d is a \ref concept_container_2d that
178also provides non-const access to its elements.
179
180\section concept_mutable_container_2d_requirments Requirements
181
182In addition to the requirements defined in \ref concept_container_2d,
183a \ref concept_mutable_container_2d also provides the following:
184
185\subsection concept_mutable_container_2d_types Types
186
187<table cellspacing=0 border=1>
188<tr><td>Reference type</td><td><tt>X::reference</tt></td>
189<td>A type that behaves as reference to the \ref
190concept_mutable_container_2d 's value type.</td>
191</tr>
192<tr>
193<td>Iterator type</td>
194<td><tt>X::iterator</tt></td>
195<td>
196
197A mutable iterator similar to Const iterator type, which can be used to
198iterate over the \ref concept_mutable_container_2d (and modify the
199elements). Typically the iterator iterates along a row, and when the
200end of one row is reached it jumps to the beginning of the next row.
201
202</td>
203</tr>
204<tr>
205<td>Column iterator type</td>
206<td><tt>X::column_iterator</tt></td>
207<td>
208A mutable iterator that can be used to modify the elements in one
209column of the \ref concept_mutable_container_2d.
210</td>
211</tr>
212<tr>
213<td>Row iterator type</td>
214<td><tt>X::row_iterator</tt></td>
215<td>
216A mutable iterator that can be used to modify the elements in one
217row of the \ref concept_mutable_container_2d.
218</td>
219</tr>
220</table>
221
222\subsection concept_mutable_container_2d_public_functions Public Functions
223
224<table cellspacing=0 border=1>
225<tr>
226<th>Name</th><th>Expression</th><th>Precondition</th><th>Return type</th>
227<th>Postcondition</th>
228</tr>
229<tr>
230<td>Beginning of range</td>
231<td><tt>a.begin()</tt></td>
232<td>&nbsp;</td>
233<td><tt>iterator</tt></td>
234<td><tt>iterator</tt> is derefenceable, unless <tt>a</tt> is empty</td>
235</tr>
236<tr>
237<td>Beginning of column</td>
238<td><tt>a.begin_column(size_t column)</tt></td>
239<td><tt>0 &lt;= column &lt; a.columns()</tt></td>
240<td><tt>column_iterator</tt></td>
241<td><tt>column_iterator</tt> is derefenceable, unless <tt>a</tt> is empty</td>
242</tr>
243<tr>
244<td>Beginning of row</td>
245<td><tt>a.begin_row(size_t row)</tt></td>
246<td><tt>0 &lt;= row &lt; a.rows()</tt></td>
247<td><tt>row_iterator</tt></td>
248<td><tt>row_iterator</tt> is derefenceable, unless <tt>a</tt> is empty</td>
249</tr>
250<tr>
251<td>End of range</td>
252<td><tt>a.end()</tt></td>
253<td>&nbsp;</td>
254<td><tt>iterator</tt></td>
255<td>&nbsp;</td>
256</tr>
257<tr>
258<td>End of column</td>
259<td><tt>a.end_column(size_t column)</tt></td>
260<td><tt>column&lt;a.columns()</tt></td>
261<td><tt>column_iterator</tt></td>
262<td>&nbsp;</td>
263</tr>
264<tr>
265<td>End of row</td>
266<td><tt>a.end_row(size_t row)</tt></td>
267<td><tt>row&lt;a.rows()</tt></td>
268<td><tt>row_iterator</tt></td>
269<td>&nbsp;</td>
270</tr>
271<tr>
272<td>Element Access</td>
273<td><tt>a(size_t row, size_t column)</tt></td>
274<td><tt>0 &lt;= row &lt; a.rows()</tt> and
275<tt>0 &lt;= column &lt; a.columns()</tt></td>
276<td><tt>reference</tt></td>
277<td>&nbsp;</td>
278</tr>
279</table>
280
281\section concept_mutable_container_2d_implementations Implementations
282
283Examples of concept \ref concept_mutable_container_2d include:
284  - theplu::yat::utility::Matrix,
285  - theplu::yat::utility::MatrixWeighted
286
287*/
288
289/**
290\page concept_distance Distance
291
292\section concept_distance_description Description
293
294\ref concept_distance is a concept for classes implementing different
295alternatives to calculate the distance between two ranges. For details
296on requirements needed for a class modelling the concept \ref
297concept_distance refer to section below, but a convenient way to
298implement a class is to use class theplu::yat::statistics::Distance as
299base class.
300
301\section concept_distance_requirments Requirements
302
303Classes modelling the concept \ref concept_distance should have a copy
304constructor
305
306\verbatim
307Distance(const Distance& d);
308\endverbatim
309
310and also implement the following public function:
311
312\verbatim
313template<typename Iterator1, typename Iterator2>
314double  operator() (Iterator1 beg1, Iterator1 end1, Iterator2 beg2) const
315\endverbatim
316
317This function should calculate and return the distance between
318elements of two ranges. The first range is given by [\a beg1, \a end1)
319and the second range starts with \a beg2 and has the same length as
320the first range. The function should support iterators that model \ref
321concept_data_iterator and \forward_traversal_iterator, in other words,
322the function should not assume any functionality not guaranteed by
323concepts \forward_traversal_iterator and \readable_iterator.
324
325As \ref concept_data_iterator should be supported, class
326should support \ref concept_weighted_iterator. Typically a \ref
327concept_distance class has a fast calculation for the case when
328neither of the two input ranges is weighted, and a separate function
329taking care of weights. A convenient way to select between unweighted and
330weighted implementations is to utilize tag structs
331theplu::yat::utility::unweighted_iterator_tag and
332theplu::yat::utility::weighted_iterator_tag as returned from meta-function
333theplu::yat::utility::weighted_if_any2.
334
335The class theplu::yat::utility::DistanceConcept an be used to test
336that a class fulfills these requirements.
337
338\section concept_distance_implementations Implementations
339
340Examples of classes modelling the concept \ref concept_distance
341include theplu::yat::statistics::PearsonDistance and
342theplu::yat::statistics::EuclideanDistance.
343
344\see \ref weighted_distance
345
346*/
347
348/**
349\page concept_neighbor_weighting Neighbor Weighting Method
350
351\section concept_neighbor_weighting_description Description
352
353\ref concept_neighbor_weighting is a concept used in connection with
354theplu::yat::classifier::KNN - classes used as the template argument
355NeighborWeighting should implement this concept.
356
357\section concept_neighbor_weighting_requirements Requirements
358
359Classes modelling the concept \ref concept_neighbor_weighting should
360be DefaultConstructible and Assignable as well as
361implement the following public function:
362
363\verbatim
364void operator()(const utility::VectorBase& distance,
365                const std::vector<size_t>& k_sorted,
366                const Target& target,
367                utility::VectorMutable& prediction) const
368\endverbatim
369
370For a test sample, this function should calculate a total vote
371(i.e. based on all k nearest neighbors) for each class. The vector \a
372distance contains the distances from a test sample to all training
373samples. The vector \a k_sorted contains the indices (for both \a
374distance and \a target) to the k training samples with the smallest
375distances to the test sample. The class for each training sample is
376given by \a target, which is sorted in the same sample order as \a
377distance. For each class the function calculates a total vote based on
378the the nearest neighbors of the test sample that belong to the
379class. The total vote for each class is stored in the vector \a
380prediction.  The function should be implemented such that nearest
381neighbors with distance infinity do not vote.
382
383\section concept_neighbor_weighting_implementations Implementations
384
385Examples of classes modelling the concept \ref
386concept_neighbor_weighting include
387theplu::yat::classifier::KNN_Uniform,
388theplu::yat::classifier::KNN_ReciprocalDistance and
389theplu::yat::classifier::KNN_ReciprocalRank.
390
391*/
392
393/**
394\page concept_weighted_iterator Weighted Iterator
395
396\section concept_weighted_iterator_description Description
397
398Most functionality in yat come in two versions: one optimized for
399speed and one weighted version allowing for missing value (see \ref
400weighted_statistics). For example, weighted containers such as
401theplu::yat::utility::MatrixWeighted and
402theplu::yat::classifier::MatrixLookupWeighted allow an easy way to
403handle missing values. Iterators that iterate over such weighted
404containers are by definition \ref concept_weighted_iterator. This
405concept is orthogonal against other iterator concepts such as Random
406Access Iterator.
407
408\section concept_weighted_iterator_requirements Requirements
409
410When implementing a new iterator that may be a \ref
411concept_weighted_iterator, there are a few things to concider.
412
413\subsection weighted_iterator_traits
414
415To decide whether an iterator is weighted, there exists a
416meta-function
417theplu::yat::utility::weighted_iterator_traits<Iterator>::type that
418will return either theplu::yat::utility::weighted_iterator_tag or
419theplu::yat::utility::unweighted_iterator_tag. The default
420implementation of this meta-function works in most cases, including on
421all std::iterators, but if you implement a new iterator make sure it
422behaves as you desire, or you need to create a specialization.
423
424\subsection iterator_traits
425
426Sometimes it is useful to have unweighted iterators behaving as though
427they were weighted. For instance,
428theplu::yat::statistics::EuclideanDistance calculates the distance
429between two ranges. If both ranges are unweighted the unweighted
430version is used, and when any of the two ranges is weighted the
431weighted version kicks in. In order to make this work also when
432comparing weighted and unweighted ranges, there must a mechanism to
433let the unweighted iterator behave as though it were weighted.
434
435This can be accomplished through
436theplu::yat::utility::iterator_traits, which enables access to data
437value as well as to weight value. For unweighted iterators the weight
438value is always equal to 1.0 and is not mutable. The default
439implementation works for most iterators including all unweighted, but
440if you implement a new weighted iterator you need to check that the
441default implementation will work for you (see class
442documentation). Otherwise, you will need to implement a
443specialization. Note that the default implementation requires that, if
444\c iterator is a weighted iterator, its \c reference must have
445member functions data() and weight(). This should not be a problem as
446long as \c reference is theplu::yat::utility::DataWeight or
447theplu::yat::utility::DataWeightProxy, but could potentially be a
448problem when creating weighted iterators with other \c reference.
449
450*/
451
452/**
453\page concept_data_iterator Data Iterator
454
455\section concept_data_iterator_description Description
456
457\ref concept_data_iterator is an iterator that is either:
458
459  - a \ref concept_weighted_iterator with value type convertible to
460theplu::yat::utility::DataWeight.
461  - an unweighted iterator with value type convertible to \c double.
462
463in addition
464
465  - \c theplu::yat::utility::weighted_iterator_traits<I> must work
466    well, which implies that iterator, \c I is a \readable_iterator
467    and \single_pass_iterator.
468
469\section concept_data_iterator_implementations Implementations
470
471Examples of concept \ref concept_data_iterator include:
472  - theplu::yat::utility::Matrix::iterator,
473  - theplu::yat::utility::MatrixWeighted::iterator,
474  - theplu::yat::classifier::MatrixLookup::const_iterator,
475  - theplu::yat::classifier::MatrixLookupWeighted::const_iterator
476*/
Note: See TracBrowser for help on using the repository browser.