source: trunk/doc/concepts.doxygen @ 1637

Last change on this file since 1637 was 1590, checked in by Peter, 13 years ago

some docs on weighted iterator - closes #395

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