source: trunk/doc/concepts.doxygen @ 1698

Last change on this file since 1698 was 1698, checked in by Peter, 12 years ago

typo

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 12.6 KB
Line 
1// $Id: concepts.doxygen 1698 2009-01-06 17:27:10Z peter $
2//
3// Copyright (C) 2008 Peter Johansson, Markus Ringnér
4// Copyright (C) 2009 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_distance
29- \subpage concept_mutable_container_2d
30- \subpage concept_neighbor_weighting
31- \subpage concept_weighted_iterator
32*/
33
34
35/**
36\page concept_container_2d Container2D
37
38\section Description
39
40\ref concept_container_2d is a <a
41href="http://www.sgi.com/tech/stl/Container.html">Container</a> that
42stores elements in a two-dimensional array (columns and rows). It
43provides element access element of a specific row and column, as well
44as iterators than can be used iterate over a specific column or row.
45
46\section Requirements
47
48A \ref concept_container_2d provides the following:
49
50\subsection Types
51
52<table cellspacing=0>
53<tr><td>Value type</td><td><tt>X::value_type</tt></td>
54<td>Type of element stored in Container.</td>
55</tr>
56<tr><td>Const reference type</td><td><tt>X::const_reference</tt></td>
57<td>A type that behaves as const reference to the \ref
58concept_container_2d 's value type.</td>
59</tr>
60<tr>
61<td>Const iterator type</td>
62<td><tt>X::const_iterator</tt></td> 
63<td>
64A read-only iterator that can be used to iterate over the entire \ref
65concept_container_2d. Typically the iterator iterates along a
66row, and when the end of one row is reached it jumps to the
67beginning of the next row.
68</td>
69</tr>
70<tr>
71<td>Const column iterator type</td>
72<td><tt>X::const_column_iterator</tt></td> 
73<td>
74A read-only iterator that can be used to examine the elements in one
75column of the \ref concept_container_2d.
76</td>
77</tr>
78<tr>
79<td>Const row iterator type</td>
80<td><tt>X::const_row_iterator</tt></td> 
81<td>
82A read-only iterator that can be used to examine the elements in one
83row of the \ref concept_container_2d.
84</td>
85</tr>
86</table>
87
88\subsection public_functions Public Functions
89
90<table cellspacing=0>
91<tr>
92<th>Name</th><th>Expression</th><th>Precondition</th><th>Return type</th>
93<th>Postcondition</th>
94</tr>
95<tr>
96<td>Beginning of range</td>
97<td><tt>a.begin()</tt></td>
98<td>&nbsp;</td>
99<td><tt>const_iterator</tt></td>
100<td>&nbsp;</td>
101</tr>
102<tr>
103<td>Beginning of column</td>
104<td><tt>a.begin_column(size_t column)</tt></td>
105<td><tt>0 &lt;= column &lt; a.columns()</tt></td>
106<td><tt>const_column_iterator</tt></td>
107<td>&nbsp;</td>
108</tr>
109<tr>
110<td>Beginning of row</td>
111<td><tt>a.begin_row(size_t row)</tt></td>
112<td><tt>0 &lt;= row &lt; a.rows()</tt></td>
113<td><tt>const_row_iterator</tt></td>
114<td>&nbsp;</td>
115</tr>
116<tr>
117<td>End of range</td>
118<td><tt>a.end()</tt></td>
119<td>&nbsp;</td>
120<td><tt>const_iterator</tt></td>
121<td>&nbsp;</td>
122</tr>
123<tr>
124<td>End of column</td>
125<td><tt>a.end_column(size_t column)</tt></td>
126<td><tt>0 &lt;= column &lt; a.columns()</tt></td>
127<td><tt>const_column_iterator</tt></td>
128<td>&nbsp;</td>
129</tr>
130<tr>
131<td>End of row</td>
132<td><tt>a.end_row(size_t row)</tt></td>
133<td><tt>0 &lt;= row &lt; a.rows()</tt></td>
134<td><tt>const_row_iterator</tt></td>
135<td>&nbsp;</td>
136</tr>
137<tr>
138<td>Columns</td>
139<td><tt>a.columns()</tt></td>
140<td>&nbsp;</td>
141<td><tt>size_t</tt></td>
142<td>&nbsp;</td>
143</tr>
144<tr>
145<td>Rows</td>
146<td><tt>a.rows()</tt></td>
147<td>&nbsp;</td>
148<td><tt>size_t</tt></td>
149<td>&nbsp;</td>
150</tr>
151<tr>
152<td>Element Access</td>
153<td><tt>a(size_t row, size_t column)</tt></td>
154<td><tt>0 &lt;= row&lt;a.rows()</tt> and
155<tt>0 &lt;= column &lt; a.columns()</tt></td>
156<td><tt>const_reference</tt></td>
157<td>&nbsp;</td>
158</tr>
159</table>
160
161\section Implementations
162
163Examples of concept \ref concept_container_2d include:
164  - theplu::yat::classifier::MatrixLookup,
165  - theplu::yat::classifier::MatrixLookupWeighted
166  - theplu::yat::classifier::KernelLookup.
167
168*/
169
170/**
171\page concept_mutable_container_2d Mutable Container2D
172
173\section Description
174
175\ref concept_mutable_container_2d is a \ref concept_container_2d that
176also provides non-const access to its elements.
177
178\section Requirements
179
180In addition to the requirements defined in \ref concept_container_2d,
181a \ref concept_mutable_container_2d also provides the following:
182
183\subsection Types
184
185<table cellspacing=0>
186<tr><td>Reference type</td><td><tt>X::reference</tt></td>
187<td>A type that behaves as reference to the \ref
188concept_mutable_container_2d 's value type.</td>
189</tr>
190<tr>
191<td>Iterator type</td>
192<td><tt>X::iterator</tt></td> 
193<td>
194
195A mutable iterator similar to Const iterator type, which can be used to
196iterate over the \ref concept_mutable_container_2d (and modify the
197elements). Typically the iterator iterates along a row, and when the
198end of one row is reached it jumps to the beginning of the next row.
199
200</td>
201</tr>
202<tr>
203<td>Column iterator type</td>
204<td><tt>X::column_iterator</tt></td> 
205<td>
206A mutable iterator that can be used to modify the elements in one
207column of the \ref concept_mutable_container_2d.
208</td>
209</tr>
210<tr>
211<td>Row iterator type</td>
212<td><tt>X::row_iterator</tt></td> 
213<td>
214A mutable iterator that can be used to modify the elements in one
215row of the \ref concept_mutable_container_2d.
216</td>
217</tr>
218</table>
219
220\subsection public_functions Public Functions
221
222<table cellspacing=0>
223<tr>
224<th>Name</th><th>Expression</th><th>Precondition</th><th>Return type</th>
225<th>Postcondition</th>
226</tr>
227<tr>
228<td>Beginning of range</td>
229<td><tt>a.begin()</tt></td>
230<td>&nbsp;</td>
231<td><tt>iterator</tt></td>
232<td><tt>iterator</tt> is derefenceable, unless <tt>a</tt> is empty</td>
233</tr>
234<tr>
235<td>Beginning of column</td>
236<td><tt>a.begin_column(size_t column)</tt></td>
237<td><tt>0 &lt;= column &lt; a.columns()</tt></td>
238<td><tt>column_iterator</tt></td>
239<td><tt>column_iterator</tt> is derefenceable, unless <tt>a</tt> is empty</td>
240</tr>
241<tr>
242<td>Beginning of row</td>
243<td><tt>a.begin_row(size_t row)</tt></td>
244<td><tt>0 &lt;= row &lt; a.rows()</tt></td>
245<td><tt>row_iterator</tt></td>
246<td><tt>row_iterator</tt> is derefenceable, unless <tt>a</tt> is empty</td>
247</tr>
248<tr>
249<td>End of range</td>
250<td><tt>a.end()</tt></td>
251<td>&nbsp;</td>
252<td><tt>iterator</tt></td>
253<td>&nbsp;</td>
254</tr>
255<tr>
256<td>End of column</td>
257<td><tt>a.end_column(size_t column)</tt></td>
258<td><tt>column&lt;a.columns()</tt></td>
259<td><tt>column_iterator</tt></td>
260<td>&nbsp;</td>
261</tr>
262<tr>
263<td>End of row</td>
264<td><tt>a.end_row(size_t row)</tt></td>
265<td><tt>row&lt;a.rows()</tt></td>
266<td><tt>row_iterator</tt></td>
267<td>&nbsp;</td>
268</tr>
269<tr>
270<td>Element Access</td>
271<td><tt>a(size_t row, size_t column)</tt></td>
272<td><tt>0 &lt;= row &lt; a.rows()</tt> and
273<tt>0 &lt;= column &lt; a.columns()</tt></td>
274<td><tt>reference</tt></td>
275<td>&nbsp;</td>
276</tr>
277</table>
278
279\section Implementations
280
281Examples of concept \ref concept_mutable_container_2d include:
282  - theplu::yat::utility::Matrix,
283  - theplu::yat::utility::MatrixWeighted
284
285*/
286
287/**
288\page concept_distance Distance
289
290\section Description
291
292\ref concept_distance is a concept for classes implementing different
293alternatives to calculate the distance between two points.
294
295\section Requirements
296
297Classes modelling the concept \ref concept_distance should implement
298the following public function:
299
300\verbatim
301template<typename Iter1, typename Iter2>
302double  operator() (Iter1 beg1, Iter1 end1, Iter2 beg2) const
303\endverbatim
304
305This function should calculate and return the distance between
306elements of two ranges. The first range is given by [\a beg1, \a end1)
307and the second range starts with \a beg2 and has the same length as
308the first range. The function should support iterators of the category
309std::forward_iterator. The function should provide both a fast
310calculation for unweighted iterators and a calculation for weighted
311iterators. The latter correspond to the case where elements in a range
312have both a value and a weight. The selection between unweighted and
313weighted implementations should utilize
314theplu::yat::utility::unweighted_iterator_tag and
315theplu::yat::utility::weighted_iterator_tag. Moreover
316theplu::yat::utility::weighted_if_any2 should be utilized to provide a
317weighted implementation if any of the two ranges is weighted, and an
318unweighted implementation when both ranges are unweighted.
319
320\section Implementations
321
322Examples of classes modelling the concept \ref concept_distance
323include theplu::yat::statistics::PearsonDistance and
324theplu::yat::statistics::EuclideanDistance.
325
326\see \ref weighted_distance
327
328*/
329
330/**
331\page concept_neighbor_weighting Neighbor Weighting Method
332
333\section Description
334
335\ref concept_neighbor_weighting is a concept used in connection with
336theplu::yat::classifier::KNN - classes used as the template argument
337NeighborWeighting should implement this concept.
338
339\section Requirements
340
341Classes modelling the concept \ref concept_neighbor_weighting should
342implement the following public function:
343 
344\verbatim   
345void operator()(const utility::VectorBase& distance,
346                const std::vector<size_t>& k_sorted,
347                const Target& target,
348                utility::VectorMutable& prediction) const
349\endverbatim
350
351For a test sample, this function should calculate a total vote
352(i.e. based on all k nearest neighbors) for each class. The vector \a
353distance contains the distances from a test sample to all training
354samples. The vector \a k_sorted contains the indices (for both \a
355distance and \a target) to the k training samples with the smallest
356distances to the test sample. The class for each training sample is
357given by \a target, which is sorted in the same sample order as \a
358distance. For each class the function calculates a total vote based on
359the the nearest neighbors of the test sample that belong to the
360class. The total vote for each class is stored in the vector \a
361prediction.  The function should be implemented such that nearest
362neighbors with distance infinity do not vote.
363
364\section Implementations
365
366Examples of classes modelling the concept \ref
367concept_neighbor_weighting include
368theplu::yat::classifier::KNN_Uniform,
369theplu::yat::classifier::KNN_ReciprocalDistance and
370theplu::yat::classifier::KNN_ReciprocalRank.
371
372*/
373
374/**
375\page concept_weighted_iterator Weighted Iterator
376
377\section Description
378
379Most functionality in yat come in two versions: one optimized for
380speed and one weighted version allowing for missing value (see \ref
381weighted_statistics). For example, weighted containers such as
382theplu::yat::utility::MatrixWeighted and
383theplu::yat::classifier::MatrixLookupWeighted allow an easy way to
384handle missing values. Iterators that iterate over such weighted
385containers are by definition \ref concept_weighted_iterator. This
386concept is orthogonal against other iterator concepts such as Random
387Access Iterator.
388
389\section Requirements
390
391When implementing a new iterator that may be a \ref
392concept_weighted_iterator, there are a few things to concider.
393
394\subsection weighted_iterator_traits
395
396To decide whether an iterator is weighted, there exists a
397meta-function
398theplu::yat::utility::weighted_iterator_traits<Iterator>::type that
399will return either theplu::yat::utility::weighted_iterator_tag or
400theplu::yat::utility::unweighted_iterator_tag. The default
401implementation of this meta-function works in most cases, including on
402all std::iterators, but if you implement a new iterator make sure it
403behaves as you desire, or you need to create a specialization.
404
405\subsection iterator_traits
406
407Sometimes it is useful to have unweighted iterators behaving as though
408they were weighted. For instance,
409theplu::yat::statistics::EuclideanDistance calculates the distance
410between two ranges. If both ranges are are unweighted the unweighted
411version is used, and when any of the two ranges is weighted the
412weighted version kicks in. In order to make this work also when
413comparing weighted and unweighted ranges, there must a mechanism to
414let the unweighted iterator behave as though it were weighted.
415
416This can be accomplished through
417theplu::yat::utility::iterator_traits, which enables access to data
418value as well as to weight value. For unweighted iterators the weight
419value is always equal to 1.0 and is not mutable. The default
420implementation works for most iterators including all unweighted, but
421if you implement a new weighted iterator you need to check that the
422default implementation will work for you (see class
423documentation). Otherwise, you will need to implement a
424specialization.
425
426*/
Note: See TracBrowser for help on using the repository browser.