source: trunk/doc/concepts.doxygen @ 2299

Last change on this file since 2299 was 2299, checked in by Peter, 11 years ago

set border in html table. fixes #622

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 13.7 KB
Line 
1// $Id: concepts.doxygen 2299 2010-07-12 15:38:46Z peter $
2//
3// Copyright (C) 2008 Jari Häkkinen, Peter Johansson, Markus Ringnér
4// Copyright (C) 2009, 2010 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 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 Requirements
49
50A \ref concept_container_2d provides the following:
51
52\subsection 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 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 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 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 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 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 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 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 Description
293
294\ref concept_distance is a concept for classes implementing different
295alternatives to calculate the distance between two points.
296
297\section Requirements
298
299Classes modelling the concept \ref concept_distance should implement
300the following public function:
301
302\verbatim
303template<typename Iter1, typename Iter2>
304double  operator() (Iter1 beg1, Iter1 end1, Iter2 beg2) const
305\endverbatim
306
307This function should calculate and return the distance between
308elements of two ranges. The first range is given by [\a beg1, \a end1)
309and the second range starts with \a beg2 and has the same length as
310the first range. The function should support iterators of the category
311std::forward_iterator. The function should provide both a fast
312calculation for unweighted iterators and a calculation for weighted
313iterators. The latter correspond to the case where elements in a range
314have both a value and a weight. The selection between unweighted and
315weighted implementations should utilize
316theplu::yat::utility::unweighted_iterator_tag and
317theplu::yat::utility::weighted_iterator_tag. Moreover
318theplu::yat::utility::weighted_if_any2 should be utilized to provide a
319weighted implementation if any of the two ranges is weighted, and an
320unweighted implementation when both ranges are unweighted.
321
322\section Implementations
323
324Examples of classes modelling the concept \ref concept_distance
325include theplu::yat::statistics::PearsonDistance and
326theplu::yat::statistics::EuclideanDistance.
327
328\see \ref weighted_distance
329
330*/
331
332/**
333\page concept_neighbor_weighting Neighbor Weighting Method
334
335\section Description
336
337\ref concept_neighbor_weighting is a concept used in connection with
338theplu::yat::classifier::KNN - classes used as the template argument
339NeighborWeighting should implement this concept.
340
341\section Requirements
342
343Classes modelling the concept \ref concept_neighbor_weighting should
344implement the following public function:
345 
346\verbatim   
347void operator()(const utility::VectorBase& distance,
348                const std::vector<size_t>& k_sorted,
349                const Target& target,
350                utility::VectorMutable& prediction) const
351\endverbatim
352
353For a test sample, this function should calculate a total vote
354(i.e. based on all k nearest neighbors) for each class. The vector \a
355distance contains the distances from a test sample to all training
356samples. The vector \a k_sorted contains the indices (for both \a
357distance and \a target) to the k training samples with the smallest
358distances to the test sample. The class for each training sample is
359given by \a target, which is sorted in the same sample order as \a
360distance. For each class the function calculates a total vote based on
361the the nearest neighbors of the test sample that belong to the
362class. The total vote for each class is stored in the vector \a
363prediction.  The function should be implemented such that nearest
364neighbors with distance infinity do not vote.
365
366\section Implementations
367
368Examples of classes modelling the concept \ref
369concept_neighbor_weighting include
370theplu::yat::classifier::KNN_Uniform,
371theplu::yat::classifier::KNN_ReciprocalDistance and
372theplu::yat::classifier::KNN_ReciprocalRank.
373
374*/
375
376/**
377\page concept_weighted_iterator Weighted Iterator
378
379\section Description
380
381Most functionality in yat come in two versions: one optimized for
382speed and one weighted version allowing for missing value (see \ref
383weighted_statistics). For example, weighted containers such as
384theplu::yat::utility::MatrixWeighted and
385theplu::yat::classifier::MatrixLookupWeighted allow an easy way to
386handle missing values. Iterators that iterate over such weighted
387containers are by definition \ref concept_weighted_iterator. This
388concept is orthogonal against other iterator concepts such as Random
389Access Iterator.
390
391\section Requirements
392
393When implementing a new iterator that may be a \ref
394concept_weighted_iterator, there are a few things to concider.
395
396\subsection weighted_iterator_traits
397
398To decide whether an iterator is weighted, there exists a
399meta-function
400theplu::yat::utility::weighted_iterator_traits<Iterator>::type that
401will return either theplu::yat::utility::weighted_iterator_tag or
402theplu::yat::utility::unweighted_iterator_tag. The default
403implementation of this meta-function works in most cases, including on
404all std::iterators, but if you implement a new iterator make sure it
405behaves as you desire, or you need to create a specialization.
406
407\subsection iterator_traits
408
409Sometimes it is useful to have unweighted iterators behaving as though
410they were weighted. For instance,
411theplu::yat::statistics::EuclideanDistance calculates the distance
412between two ranges. If both ranges are unweighted the unweighted
413version is used, and when any of the two ranges is weighted the
414weighted version kicks in. In order to make this work also when
415comparing weighted and unweighted ranges, there must a mechanism to
416let the unweighted iterator behave as though it were weighted.
417
418This can be accomplished through
419theplu::yat::utility::iterator_traits, which enables access to data
420value as well as to weight value. For unweighted iterators the weight
421value is always equal to 1.0 and is not mutable. The default
422implementation works for most iterators including all unweighted, but
423if you implement a new weighted iterator you need to check that the
424default implementation will work for you (see class
425documentation). Otherwise, you will need to implement a
426specialization. Note that the default implementation requires that, if
427\c iterator is a weighted iterator, \c iterator::reference must have
428member functions data() and weight(). This should not be a problem as
429long as \c iterator::reference is theplu::yat::utility::DataWeight or
430theplu::yat::utility::DataWeightProxy, but could potentially be a
431problem when creating weighted iterators with other \c ::reference.
432
433*/
434
435/**
436\page concept_data_iterator Data Iterator
437
438\section Description
439
440\ref concept_data_iterator is an iterator that comes in two shapes:
441
442  - it is either a \ref concept_weighted_iterator with value type
443convertible to theplu::yat::utility::DataWeight
444  - it is an unweighted iterator with value type
445convertible to \c double.
446
447\section Implementations
448
449Examples of concept \ref concept_data_iterator include:
450  - theplu::yat::utility::Matrix::iterator,
451  - theplu::yat::utility::MatrixWeighted::iterator,
452  - theplu::yat::classifier::MatrixLookup::const_iterator,
453  - theplu::yat::classifier::MatrixLookupWeighted::const_iterator
454*/
Note: See TracBrowser for help on using the repository browser.