1 // ==========================================================================
2 //                 SeqAn - The Library for Sequence Analysis
3 // ==========================================================================
4 // Copyright (c) 2006-2018, Knut Reinert, FU Berlin
5 // All rights reserved.
6 //
7 // Redistribution and use in source and binary forms, with or without
8 // modification, are permitted provided that the following conditions are met:
9 //
10 //     * Redistributions of source code must retain the above copyright
11 //       notice, this list of conditions and the following disclaimer.
12 //     * Redistributions in binary form must reproduce the above copyright
13 //       notice, this list of conditions and the following disclaimer in the
14 //       documentation and/or other materials provided with the distribution.
15 //     * Neither the name of Knut Reinert or the FU Berlin nor the names of
16 //       its contributors may be used to endorse or promote products derived
17 //       from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 // ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE
23 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
29 // DAMAGE.
30 //
31 // ==========================================================================
32 // Author: Manuel Holtgrewe <manuel.holtgrewe@fu-berlin.de>
33 // ==========================================================================
34 // Implementation of the SeqAn accumulator code.
35 //
36 // While Boost also has a versatile accumulator library, we create our own
37 // since it is much simpler and focused on the requirements in sequence
38 // analysis algorithms than then Boost one.
39 // ==========================================================================
40 
41 #ifndef INCLUDE_SEQAN_MISC_ACCUMULATORS_H_
42 #define INCLUDE_SEQAN_MISC_ACCUMULATORS_H_
43 
44 #include <seqan/sequence.h>
45 
46 namespace seqan {
47 
48 // ============================================================================
49 // Forwards
50 // ============================================================================
51 
52 template <typename T, typename TTag> struct Result;
53 
54 // ============================================================================
55 // Tags, Classes, Enums
56 // ============================================================================
57 
58 struct AccuAverage_;
59 typedef Tag<AccuAverage_> AccuAverage;
60 
61 struct AccuSum_;
62 typedef Tag<AccuSum_> AccuSum;
63 
64 struct AccuCount_;
65 typedef Tag<AccuCount_> AccuCount;
66 
67 /*!
68  * @class Accumulator
69  * @headerfile <seqan/misc/accumulators.h>
70  * @brief Accumulator base class.
71  *
72  * @signature template <typename TValue, typename TSpec>
73  *            struct Accumulator;
74  *
75  * @tparam TSpec  The specialization tag.
76  * @tparam TValue The type of the values to accumulate.
77  *
78  * Accumulators are for computing statistics on streams of values.
79  *
80  * Currently, this is only meant for accumulating integers.
81  */
82 
83 template <typename TValue, typename TSpec>
84 struct Accumulator;
85 
86 /*!
87  * @class AverageAccumulator
88  * @extends Accumulator
89  * @headerfile <seqan/misc/accumulators.h>
90  * @brief Accumulator for computing averages.
91  *
92  * @signature template <typename TValue>
93  *            struct Accumulator<TValue, AccuAverage>;
94  *
95  * @tparam TValue The type of the values to compute the average of.
96  *
97  * The average of an empty sequence is defined to be 0.
98  *
99  * @section Examples
100  *
101  * This program shows how to use the Average Accumulator.
102  *
103  * @code{.cpp}
104  * Accumulator<int, AccuAverage> acc;
105  * push(acc, 1);
106  * push(acc, 2);
107  * push(acc, 3);
108  * std::cout << "average: " << average(acc) << "\n"
109  *           << "sum:     " << sum(acc) << "\n"
110  *           << "count:   " << count(acc) << "\n";
111  * @endcode
112  *
113  * The output is then:
114  *
115  * @code{.console}
116  * average: 2
117  * sum:     6
118  * count:   3
119  * @endcode
120  */
121 
122 template <typename TValue>
123 struct Accumulator<TValue, AccuAverage>
124 {
125     typedef typename Result<Accumulator<TValue, AccuAverage>, AccuSum>::Type TAccuSum_;
126 
127     TAccuSum_ sum_;
128     unsigned count_;
129 
130     Accumulator() : sum_(0), count_(0) {}
131 };
132 
133 // ============================================================================
134 // Metafunctions
135 // ============================================================================
136 
137 // ----------------------------------------------------------------------------
138 // Metafunction Value                                       Average Accumulator
139 // ----------------------------------------------------------------------------
140 
141 /*!
142  * @mfn Accumulator#Value
143  * @brief Return the type of the values to accumulate.
144  *
145  * @signature Value<TAccumulator>::Type;
146  *
147  * @tparam TAccumulator The Accumulator type to query.
148  *
149  * @return Type The value type.
150  */
151 
152 template <typename TValue>
153 struct Value<Accumulator<TValue, AccuAverage> >
154 {
155     typedef double Type;
156 };
157 
158 template <typename TValue>
159 struct Value<Accumulator<TValue, AccuAverage> const > : Value<Accumulator<TValue, AccuAverage> >
160 {};
161 
162 // ----------------------------------------------------------------------------
163 // Metafunction Result                                      Average Accumulator
164 // ----------------------------------------------------------------------------
165 
166 // TODO(holtgrew): This could probably go to basic, as a part of an "AlgorithmState" concept?
167 
168 /*!
169  * @mfn Accumulator#Result
170  * @brief Return the type for accumulation results.
171  *
172  * @signature Result<TAccumulator>::Type;
173  *
174  * @tparam TAccumulator The Accumulator type to query.
175  *
176  * @return Type The result type.
177  */
178 
179 template <typename T, typename TTag = void>
180 struct Result;
181 
182 // ----------------------------------------------------------------------------
183 // Metafunction Result                                      Average Accumulator
184 // ----------------------------------------------------------------------------
185 
186 template <typename TValue>
187 struct Result<Accumulator<TValue, AccuAverage>, AccuAverage>
188 {
189     typedef double Type;
190 };
191 
192 template <typename TValue>
193 struct Result<Accumulator<TValue, AccuAverage> const, AccuAverage> : Result<Accumulator<TValue, AccuAverage>, AccuAverage>
194 {};
195 
196 template <typename TValue>
197 struct Result<Accumulator<TValue, AccuAverage>, AccuCount>
198 {
199     typedef unsigned Type;
200 };
201 
202 template <typename TValue>
203 struct Result<Accumulator<TValue, AccuAverage> const, AccuCount> : Result<Accumulator<TValue, AccuAverage>, AccuCount>
204 {};
205 
206 template <typename TValue>
207 struct Result<Accumulator<TValue, AccuAverage>, AccuSum>
208 {
209     typedef typename IfC<Is<IntegerConcept<TValue> >::VALUE,
210                          int64_t,
211                          double>::Type Type;
212 };
213 
214 template <typename TValue>
215 struct Result<Accumulator<TValue, AccuAverage> const, AccuSum> : Result<Accumulator<TValue, AccuAverage>, AccuSum>
216 {};
217 
218 // ============================================================================
219 // Functions
220 // ============================================================================
221 
222 // ----------------------------------------------------------------------------
223 // Function clear()                                                 Accumulator
224 // ----------------------------------------------------------------------------
225 
226 // ----------------------------------------------------------------------------
227 // Function push()                                                  Accumulator
228 // ----------------------------------------------------------------------------
229 
230 /*!
231  * @fn Accumulator#push
232  * @brief Include value into sequence of values to accumulate.
233  *
234  * @signature void push(acc, x);
235  *
236  * @param[in,out] acc The Accumulator to push the value to.
237  * @param[in]     x   The value to include in the accumulation (@link IntegerConcept @endlink).
238  */
239 
240 // ----------------------------------------------------------------------------
241 // Function clear()                                                 Accumulator
242 // ----------------------------------------------------------------------------
243 
244 /*!
245  * @fn Accumulator#clear
246  * @brief Clear the current accumulator state.
247  *
248  * @signature void clear(acc);
249  *
250  * @param[in,out] acc The Accumulator to clear.
251  */
252 
253 // ----------------------------------------------------------------------------
254 // Function clear()                                         Average Accumulator
255 // ----------------------------------------------------------------------------
256 
257 template <typename TValue>
258 inline void
259 clear(Accumulator<TValue, AccuAverage> & accumulator)
260 {
261     accumulator.sum_ = 0;
262     accumulator.count_ = 0;
263 }
264 
265 // ----------------------------------------------------------------------------
266 // Function push()                                          Average Accumulator
267 // ----------------------------------------------------------------------------
268 
269 template <typename TValue, typename TValue2>
270 inline void
271 push(Accumulator<TValue, AccuAverage> & acc, TValue2 value)
272 {
273     typedef typename Result<Accumulator<TValue, AccuAverage>, AccuSum>::Type TAccuSum;
274     acc.sum_ += static_cast<TAccuSum>(value);
275     acc.count_ += 1;
276 }
277 
278 // ----------------------------------------------------------------------------
279 // Function average()                                       Average Accumulator
280 // ----------------------------------------------------------------------------
281 
282 /*!
283  * @fn AverageAccumulator#average
284  * @brief Return the average of the included values.
285  *
286  * @signature TResult average(acc);
287  *
288  * @param[in] acc The Accumulator to compute the average for.
289  *
290  * @return TResult The average of the values (Metafunction: @link Accumulator#Result @endlink).
291  */
292 
293 template <typename TValue>
294 inline typename Result<Accumulator<TValue, AccuAverage>, AccuAverage>::Type
295 average(Accumulator<TValue, AccuAverage> const & acc)
296 {
297     typedef typename Result<Accumulator<TValue, AccuAverage>, AccuAverage>::Type TResult;
298     if (acc.count_ == 0u)
299         return 0;
300     return static_cast<TResult>(acc.sum_ / static_cast<TResult>(acc.count_));
301 }
302 
303 // ----------------------------------------------------------------------------
304 // Function sum()                                           Average Accumulator
305 // ----------------------------------------------------------------------------
306 
307 /*!
308  * @fn AverageAccumulator#sum
309  * @brief Return the sum of the included values.
310  *
311  * @signature TResult sum(acc);
312  *
313  * @param[in] acc The Accumulator to compute the sum for.
314  *
315  * @return TResult The sum of the values (Metafunction: @link Accumulator#Result @endlink).
316  */
317 
318 template <typename TValue>
319 inline typename Result<Accumulator<TValue, AccuAverage>, AccuSum>::Type
320 sum(Accumulator<TValue, AccuAverage> const & acc)
321 {
322     return acc.sum_;
323 }
324 
325 // ----------------------------------------------------------------------------
326 // Function count()                                         Average Accumulator
327 // ----------------------------------------------------------------------------
328 
329 /*!
330  * @fn AverageAccumulator#count
331  * @brief Return the number of included values.
332  *
333  * @signature TResult count(acc);
334  *
335  * @param[in] count The number of values pushed to the accumulator.
336  *
337  * @return TResult The number of pushed values (Metafunction: @link Accumulator#Result @endlink).
338  */
339 
340 template <typename TValue>
341 inline typename Result<Accumulator<TValue, AccuAverage>, AccuCount>::Type
342 count(Accumulator<TValue, AccuAverage> const & acc)
343 {
344     return acc.count_;
345 }
346 
347 }  // namespace seqan
348 
349 #endif  // #ifndef INCLUDE_SEQAN_MISC_ACCUMULATORS_H_
350