source: trunk/doc/concepts.doxygen @ 1547

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

refs #448

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 10.2 KB
Line 
1// $Id: concepts.doxygen 1547 2008-10-03 20:27:40Z 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*/
31
32
33/**
34\page concept_container_2d Container2D
35
36\section Description
37
38\ref concept_container_2d is a <a
39href="http://www.sgi.com/tech/stl/Container.html">Container</a> that
40stores elements in a two-dimensional array (columns and rows). It
41provides element access element of a specific row and column, as well
42as iterators than can be used iterate over a specific column or row.
43
44\section Requirements
45
46A \ref concept_container_2d provides the following:
47
48\subsection Types
49
50<table cellspacing=0>
51<tr><td>Const reference type</td><td><tt>X::const_reference</tt></td>
52<td>A type that behaves as const reference to the \ref
53concept_container_2d 's value type.</td>
54</tr>
55<tr>
56<td>Const iterator type</td>
57<td><tt>X::const_iterator</tt></td> 
58<td>
59A read-only iterator that can be used to iterate over the entire \ref
60concept_container_2d. Typically the iterator iterates along a
61row, and when the end of one row is reached it jumps to the
62beginning of the next row.
63</td>
64</tr>
65<tr>
66<td>Const column iterator type</td>
67<td><tt>X::const_column_iterator</tt></td> 
68<td>
69A read-only iterator that can be used to examine the elements in one
70column of the \ref concept_container_2d.
71</td>
72</tr>
73<tr>
74<td>Const row iterator type</td>
75<td><tt>X::const_row_iterator</tt></td> 
76<td>
77A read-only iterator that can be used to examine the elements in one
78row of the \ref concept_container_2d.
79</td>
80</tr>
81</table>
82
83\subsection public_functions Public Functions
84
85<table cellspacing=0>
86<tr>
87<th>Name</th><th>Expression</th><th>Precondition</th><th>Return type</th>
88<th>Postcondition</th>
89</tr>
90<tr>
91<td>Beginning of range</td>
92<td><tt>a.begin()</tt></td>
93<td>&nbsp;</td>
94<td><tt>const_iterator</tt></td>
95<td>&nbsp;</td>
96</tr>
97<tr>
98<td>Beginning of column</td>
99<td><tt>a.begin_column(size_t column)</tt></td>
100<td><tt>0 &lt;= column &lt; a.columns()</tt></td>
101<td><tt>const_column_iterator</tt></td>
102<td>&nbsp;</td>
103</tr>
104<tr>
105<td>Beginning of row</td>
106<td><tt>a.begin_row(size_t row)</tt></td>
107<td><tt>0 &lt;= row &lt; a.rows()</tt></td>
108<td><tt>const_row_iterator</tt></td>
109<td>&nbsp;</td>
110</tr>
111<tr>
112<td>End of range</td>
113<td><tt>a.end()</tt></td>
114<td>&nbsp;</td>
115<td><tt>const_iterator</tt></td>
116<td>&nbsp;</td>
117</tr>
118<tr>
119<td>End of column</td>
120<td><tt>a.end_column(size_t column)</tt></td>
121<td><tt>0 &lt;= column &lt; a.columns()</tt></td>
122<td><tt>const_column_iterator</tt></td>
123<td>&nbsp;</td>
124</tr>
125<tr>
126<td>End of row</td>
127<td><tt>a.end_row(size_t row)</tt></td>
128<td><tt>0 &lt;= row &lt; a.rows()</tt></td>
129<td><tt>const_row_iterator</tt></td>
130<td>&nbsp;</td>
131</tr>
132<tr>
133<td>Columns</td>
134<td><tt>a.columns()</tt></td>
135<td>&nbsp;</td>
136<td><tt>size_t</tt></td>
137<td>&nbsp;</td>
138</tr>
139<tr>
140<td>Rows</td>
141<td><tt>a.rows()</tt></td>
142<td>&nbsp;</td>
143<td><tt>size_t</tt></td>
144<td>&nbsp;</td>
145</tr>
146<tr>
147<td>Element Access</td>
148<td><tt>a(size_t row, size_t column)</tt></td>
149<td><tt>0 &lt;= row&lt;a.rows()</tt> and
150<tt>0 &lt= column &lt; a.columns()</tt></td>
151<td><tt>const_reference</tt></td>
152<td>&nbsp;</td>
153</tr>
154</table>
155
156\section Implementations
157
158Examples of concept \ref concept_container_2d include:
159  - theplu::yat::classifier::MatrixLookup,
160  - theplu::yat::classifier::MatrixLookupWeighted
161  - theplu::yat::classifier::KernelLookup.
162
163*/
164
165/**
166\page concept_mutable_container_2d Mutable Container2D
167
168\section Description
169
170\ref concept_mutable_container_2d is a \ref concept_container_2d that
171also provides non-const access to its elements.
172
173\section Requirements
174
175In addition to the requirements defined in \ref concept_container_2d,
176a \ref concept_mutable_container_2d also provides the following:
177
178\subsection Types
179
180<table cellspacing=0>
181<tr><td>Reference type</td><td><tt>X::reference</tt></td>
182<td>A type that behaves as reference to the \ref
183concept_mutable_container_2d 's value type.</td>
184</tr>
185<tr>
186<td>Iterator type</td>
187<td><tt>X::iterator</tt></td> 
188<td>
189
190A mutable iterator similar to Const iterator type, which can be used to
191iterate over the \ref concept_mutable_container_2d (and modify the
192elements). Typically the iterator iterates along a row, and when the
193end of one row is reached it jumps to the beginning of the next row.
194
195</td>
196</tr>
197<tr>
198<td>Column iterator type</td>
199<td><tt>X::column_iterator</tt></td> 
200<td>
201A mutable iterator that can be used to modify the elements in one
202column of the \ref concept_mutable_container_2d.
203</td>
204</tr>
205<tr>
206<td>Row iterator type</td>
207<td><tt>X::row_iterator</tt></td> 
208<td>
209A mutable iterator that can be used to modify the elements in one
210row of the \ref concept_mutable_container_2d.
211</td>
212</tr>
213</table>
214
215\subsection public_functions Public Functions
216
217<table cellspacing=0>
218<tr>
219<th>Name</th><th>Expression</th><th>Precondition</th><th>Return type</th>
220<th>Postcondition</th>
221</tr>
222<tr>
223<td>Beginning of range</td>
224<td><tt>a.begin()</tt></td>
225<td>&nbsp;</td>
226<td><tt>iterator</tt></td>
227<td><tt>iterator</tt> is derefenceable, unless <tt>a</tt> is empty</td>
228</tr>
229<tr>
230<td>Beginning of column</td>
231<td><tt>a.begin_column(size_t column)</tt></td>
232<td><tt>0 &lt;= column &lt; a.columns()</tt></td>
233<td><tt>column_iterator</tt></td>
234<td><tt>column_iterator</tt> is derefenceable, unless <tt>a</tt> is empty</td>
235</tr>
236<tr>
237<td>Beginning of row</td>
238<td><tt>a.begin_row(size_t row)</tt></td>
239<td><tt>0 &lt;= row &lt; a.rows()</tt></td>
240<td><tt>row_iterator</tt></td>
241<td><tt>row_iterator</tt> is derefenceable, unless <tt>a</tt> is empty</td>
242</tr>
243<tr>
244<td>End of range</td>
245<td><tt>a.end()</tt></td>
246<td>&nbsp;</td>
247<td><tt>iterator</tt></td>
248<td>&nbsp;</td>
249</tr>
250<tr>
251<td>End of column</td>
252<td><tt>a.end_column(size_t column)</tt></td>
253<td><tt>column&lt;a.columns()</tt></td>
254<td><tt>column_iterator</tt></td>
255<td>&nbsp;</td>
256</tr>
257<tr>
258<td>End of row</td>
259<td><tt>a.end_row(size_t row)</tt></td>
260<td><tt>row&lt;a.rows()</tt></td>
261<td><tt>row_iterator</tt></td>
262<td>&nbsp;</td>
263</tr>
264<tr>
265<td>Element Access</td>
266<td><tt>a(size_t row, size_t column)</tt></td>
267<td><tt>0 &lt;= row &lt; a.rows()</tt> and
268<tt>0 &lt;= column &lt; a.columns()</tt></td>
269<td><tt>reference</tt></td>
270<td>&nbsp;</td>
271</tr>
272</table>
273
274\section Implementations
275
276Examples of concept \ref concept_mutable_container_2d include:
277  - theplu::yat::utility::Matrix,
278  - theplu::yat::utility::MatrixWeighted
279
280*/
281
282/**
283\page concept_distance Distance
284
285\section Description
286
287\ref concept_distance is a concept for classes implementing different
288alternatives to calculate the distance between two points.
289
290\section Requirements
291
292Classes modelling the concept \ref concept_distance should implement
293the following public function:
294
295\verbatim
296template<typename Iter1, typename Iter2>
297double  operator() (Iter1 beg1, Iter1 end1, Iter2 beg2) const
298\endverbatim
299
300This function should calculate and return the distance between
301elements of two ranges. The first range is given by [\a beg1, \a end1)
302and the second range starts with \a beg2 and has the same length as
303the first range. The function should support iterators of the category
304std::forward_iterator. The function should provide both a fast
305calculation for unweighted iterators and a calculation for weighted
306iterators. The latter correspond to the case where elements in a range
307have both a value and a weight. The selection between unweighted and
308weighted implementations should utilize
309theplu::yat::utility::unweighted_iterator_tag and
310theplu::yat::utility::weighted_iterator_tag. Moreover
311theplu::yat::utility::weighted_if_any2 should be utilized to provide a
312weighted implementation if any of the two ranges is weighted, and an
313unweighted implementation when both ranges are unweighted.
314
315\section Implementations
316
317Examples of classes modelling the concept \ref concept_distance
318include theplu::yat::statistics::PearsonDistance and
319theplu::yat::statistics::EuclideanDistance.
320
321\see \ref weighted_distance
322
323*/
324
325/**
326\page concept_neighbor_weighting Neighbor Weighting Method
327
328\section Description
329
330\ref concept_neighbor_weighting is a concept used in connection with
331theplu::yat::classifier::KNN - classes used as the template argument
332NeighborWeighting should implement this concept.
333
334\section Requirements
335
336Classes modelling the concept \ref concept_neighbor_weighting should
337implement the following public function:
338 
339\verbatim   
340void operator()(const utility::VectorBase& distance,
341                const std::vector<size_t>& k_sorted,
342                const Target& target,
343                utility::VectorMutable& prediction) const
344\endverbatim
345
346For a test sample, this function should calculate a total vote
347(i.e. based on all k nearest neighbors) for each class. The vector \a
348distance contains the distances from a test sample to all training
349samples. The vector \a k_sorted contains the indices (for both \a
350distance and \a target) to the k training samples with the smallest
351distances to the test sample. The class for each training sample is
352given by \a target, which is sorted in the same sample order as \a
353distance. For each class the function calculates a total vote based on
354the the nearest neighbors of the test sample that belong to the
355class. The total vote for each class is stored in the vector \a
356prediction.  The function should be implemented such that nearest
357neighbors with distance infinity do not vote.
358
359\section Implementations
360
361Examples of classes modelling the concept \ref
362concept_neighbor_weighting include
363theplu::yat::classifier::KNN_Uniform,
364theplu::yat::classifier::KNN_ReciprocalDistance and
365theplu::yat::classifier::KNN_ReciprocalRank.
366
367*/
Note: See TracBrowser for help on using the repository browser.