source: trunk/doc/concepts.doxygen @ 1878

Last change on this file since 1878 was 1797, checked in by Peter, 13 years ago

updating copyright statements

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