source: trunk/doc/concepts.doxygen @ 2339

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

refs #627 extending NeighborWeighting? concept to require defaulf constructor and assign operator. Added a archetype class in test.

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