Debian Codegraph @

CHistogram.h

raw
1 /* BaitFisher (version 1.2.8) a program for designing DNA target enrichment baits
2 * BaitFilter (version 1.0.6) a program for selecting optimal bait regions
3 * Copyright 2013-2017 by Christoph Mayer
4 *
5 * This source file is part of the BaitFisher-package.
6 *
7 * This program is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * This program 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
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with BaitFisher. If not, see <http://www.gnu.org/licenses/>.
19 *
20 *
21 * For any enquiries send an Email to Christoph Mayer
22 * [email protected]
23 *
24 * When publishing work that is based on the results please cite:
25 * Mayer et al. 2016: BaitFisher: A software package for multi-species target DNA enrichment probe design
26 *
27 */
28 #ifndef CHISTOGRAM_H
29 #define CHISTOGRAM_H
30
31 // This is the CHistogram class written by Christoph Mayer, Forschungsmuseum Alexander Koenig, Bonn, Germany.
32 // Discription:
33 // This class allowes different binning schemes:
34 // 1) User supplied number of bins together with lower and upper value.
35 // IMPORTANT: The lower value is inclusive, the upper value is exclusive.
36 // Therefore, a value equal to the upper value cannot be added
37 // to the histrogram data.
38 // If this is a problem, increase the upper value, or take
39 // a different constructor. See below.
40 // 2) Vector or range of data. From this the lower and upper bound
41 // are determined automatically. Number fo bins or automatic binning
42 // if the number of bins parameter has certain negative values.
43 // 3) Discrete data. In this case the data is not binned when it is added,
44 // but stored in a map. The binning is performed upon request.
45
46
47
48
49 #include <iostream>
50 #include <vector>
51 #include <map>
52 #include <cmath>
53 #include <cctype>
54 #include <iterator>
55 #include <cstdlib>
56 #include <algorithm>
57 #include "statistic_functions.h"
58
59 #define EPSS 0.00000000001;
60
61
62
63
64
65
66
67
68 inline bool greater_than_pair(const std::pair<double, unsigned> &a, const std::pair<double, unsigned> &b )
69 {
70 return a.second > b.second;
71 }
72
73
74
75
76 inline void add_or_count(std::map<double, unsigned> &m, double &x)
77 {
78 std::map<double,unsigned>::iterator it;
79
80 it = m.find(x);
81 if (it == m.end() )
82 {
83 m[x] = 1;
84 }
85 else
86 {
87 ++it->second;
88 }
89 }
90
91
92
93
94 class CHistogram
95
96 {
97 private:
98 double a; // Inclusive range minimum
99 double b; // Exclusive range maximum
100 unsigned bins;
101 double step;
102 unsigned entries;
103
104 std::vector<unsigned> data;
105
106 bool discrete_data; // is determined in initialisation. Switched on with -10.
107 std::map<double, unsigned> discrete_hist_data;
108
109 private:
110 bool add_intern_non_discrete(double x)
111 {
112 // Be careful: If x==b this is allowed, but it places
113 // this hit into the
114
115 if (x < a || x >= b)
116 {
117 if (x == b)
118 std::cerr << "Warning: CHistrogram::add_intern_non_discrete data.siz\n"
119 << " Data points that are added must be exclusive the upper bound of the given range.\n\n";
120 return false;
121 }
122
123 ++entries;
124
125 unsigned bin = (x-a)/step;
126 // std::cerr << "HH " << bin << " " << data.size() << std::endl;
127
128 ++data[bin];
129 return true;
130 }
131
132 // Adds the value to the discete data map.
133 // Number of bins as well as a and b are not changed.
134 bool add_intern_discrete_no_update(double x)
135 {
136 ++entries;
137 add_or_count(discrete_hist_data, x);
138 return true;
139 }
140
141 void update_a_b_bins_discrete_data()
142 {
143 // Remember: The discrete data is stored in an automatically sorted map.
144 // Therefore, the bounds are determined from the first and last element.
145
146 // Determine a, b and bins:
147 a = discrete_hist_data.begin()->first;
148 b = discrete_hist_data.rbegin()->first;
149
150 bins = discrete_hist_data.size();
151 }
152
153
154 public:
155 void init_with_vector(const std::vector<double> &vals, int bins_param=0)
156 {
157 init_with_range(vals.begin(), vals.end(), vals.size(), bins_param);
158 }
159
160
161 template <typename T>
162 void init_with_range(T it_beg, // pointer or iterator to first element
163 T it_end, // pointer or iterator to element behind last element
164 unsigned num_range_elements, // number of elements in range
165 int bins_param=0) // number of bins or if <=0 specifies the method
166 // to determine this number
167 {
168 double mi, ma, me, sd;
169
170 discrete_data = false;
171
172 if (num_range_elements == 0) // Fill in some dummy values so that everything is well defined. Pratically this does not make sense, but should prevent other classes using this data from crashing.
173 {
174 a = 0;
175 b = 1;
176 data.push_back(0);
177 bins = 1;
178 step = 1;
179
180 return;
181 }
182
183 mi = ma = 0; // This code silences the used uninitialized warning of some compilers. It is not necessary, since the two variables are initialized in
184 // range_min_max as the name suggests.
185
186 range_min_max(it_beg, it_end, mi, ma);
187
188 // Special case: Only one category and automatic number of bins, but not discrete data
189 // In principle this is a special case of discrete data but not explicitly mentioned.
190 if (bins_param != -10 && bins_param <= 0 && mi== ma)
191 bins_param = 1;
192
193
194
195 // Formulas for auto bins number: http://en.wikipedia.org/wiki/Histogram
196
197 if (bins_param == 0) // Sturges formula -- can perform poorly if n < 30.
198 {
199 bins = ceil(log(num_range_elements)/log(2)+1);
200 }
201 else if (bins_param == -1) // Scotts formula
202 {
203 range_mean_sd(it_beg, it_end, me, sd);
204 bins = 3.5*sd/pow(num_range_elements, 1./3.);
205 if (bins < 1)
206 bins = 1;
207 }
208 else if (bins_param == -2) // sqrt formula
209 {
210 bins = sqrt(num_range_elements);
211 }
212 else if (bins_param == -3) // Freedman-Diaconis' formula // Not implemented
213 {
214 bins = 1;
215 }
216 else if (bins_param == -4) // minimization of risk function // Not implemented
217 {
218 bins = 1;
219 }
220 else if (bins_param == -10) // Each value gets its own bin
221 {
222 discrete_data = true;
223 }
224 else if (bins_param > 0)
225 {
226 bins = bins_param;
227 }
228 else
229 {
230 std::cerr << "Error: the init_param parameter is negative, but its value does not specify a method. This needs to be corrected." << std::endl;
231 exit(-133);
232 }
233
234 // We have minimum (mi), maximum (ma) and number of bins.
235 // Now we determine the step size as well as lower and upper bound (a,b).
236
237 if (!discrete_data) // Add non discrete values:
238 {
239 if (bins > 1)
240 {
241 step = (ma-mi)/(bins-1.0);
242 a = mi - 0.5*step;
243 b = ma + 0.5*step;
244 }
245 else
246 {
247 step = 1.0; // fantasy value
248 a = mi - 0.5*step;
249 b = ma + 0.5*step;
250 }
251
252 /* std::cerr << "--a " << a << std::endl; */
253 /* std::cerr << "--b " << b << std::endl; */
254 /* std::cerr << "--bins " << bins << std::endl; */
255 /* std::cerr << "--step " << step << std::endl; */
256
257
258 data = std::vector<unsigned>(bins, 0);
259
260 while (it_beg != it_end)
261 {
262 if (!add_intern_non_discrete(*it_beg) )
263 {
264 std::cerr << "Internal error: Value out of range when building the histgram.\n" << std::endl;
265 exit(-144);
266 }
267 ++it_beg;
268 }
269 }
270 else // Add dicrete values
271 {
272 step = 0;
273 // Add all values to map:
274 while (it_beg != it_end)
275 {
276 add_intern_discrete_no_update(*it_beg);
277 ++it_beg;
278 }
279 update_a_b_bins_discrete_data();
280 }
281
282
283 }
284
285 // Constructor with: lower and upper value as well as the number of
286 // equidistant bins.
287 // Here we do not allow to determine the number of bins automatically for the simple reason:
288 // The number of necessary bins can only be determined if the number of data points is known
289 // which is not assumed here.
290 CHistogram(double a_param, double b_param, int bins_param):
291 a(a_param), b(b_param), bins(bins_param), entries(0), data(bins_param, 0)
292 {
293 if (bins_param < 1)
294 {
295 std::cerr << "Critical error in constructor of CHistogram. Parameter bins_param must be positive here.\n" << std::endl;
296 exit(-143);
297 }
298
299 discrete_data = false;
300 step = (b-a)/bins;
301
302 // Adds no data.
303 }
304
305 // Constructor with: range or vector as well as the bins_param
306 // if bins_param < 1: then the parameter specifies the method to determine the number
307 // of bins automatically.
308 // 0: Sturges formula -- can perform poorly if n < 30.
309 // -1: Scotts formula
310 // -2: sqrt formula
311 // -3: Freedman-Diaconis' formula // Not implemented
312 // -4: minimization of risk function // Not implemented
313 // if bins_param > 1: this specifies the actual number of bins
314
315 CHistogram(const std::vector<double> &vals, int bins_param=0):entries(0)
316 {
317 init_with_range(vals.begin(), vals.end(), vals.size(), bins_param);
318 }
319
320 CHistogram(const std::vector<float> &vals, int bins_param=0):entries(0)
321 {
322 init_with_range(vals.begin(), vals.end(), vals.size(), bins_param);
323 }
324
325 CHistogram(const std::vector<unsigned> &vals, int bins_param=0):entries(0)
326 {
327 init_with_range(vals.begin(), vals.end(), vals.size(), bins_param);
328 }
329
330 template <typename T>
331 CHistogram(T it_beg,
332 T it_end,
333 int bins_param=0):entries(0)
334 {
335 init_with_range(it_beg, it_end, std::distance(it_beg, it_end), bins_param);
336 }
337
338 double get_lower()
339 {
340 return a;
341 }
342
343 double get_upper()
344 {
345 return b;
346 }
347
348 unsigned get_bins()
349 {
350 return bins;
351 }
352
353 double get_binsize()
354 {
355 return step;
356 }
357
358 // This function should be reimplemented in a cleaner way!!!
359 // The use of the data field to store disc
360 const std::vector<unsigned> &get_histogram_data()
361 {
362 if (discrete_data) // data needs to be prepared:
363 {
364 data.clear();
365
366 std::map<double, unsigned>::iterator it_beg, it_end;
367
368 it_beg = discrete_hist_data.begin();
369 it_end = discrete_hist_data.end();
370
371 while (it_beg != it_end)
372 {
373 data.push_back(it_beg->second);
374 ++it_beg;
375 }
376 }
377 return data;
378 }
379
380 void get_bin_coords(std::vector<double> &v)
381 {
382 /* std::cerr << "a " << a << std::endl; */
383 /* std::cerr << "b " << b << std::endl; */
384 /* std::cerr << "bins " << bins << std::endl; */
385 /* std::cerr << "step " << step << std::endl; */
386
387
388 unsigned i;
389
390 v.clear();
391
392 if (!discrete_data)
393 {
394 for (i=0; i<bins; ++i)
395 {
396 v.push_back(a+(i+0.5)*step);
397 }
398 }
399 else
400 {
401 std::map<double, unsigned>::iterator it_beg, it_end;
402
403 it_beg = discrete_hist_data.begin();
404 it_end = discrete_hist_data.end();
405
406 while (it_beg != it_end)
407 {
408 v.push_back(it_beg->first);
409 ++it_beg;
410 }
411 }
412 }
413
414
415 //XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
416 // old code - needs revision. See method to compute coordinates
417 /* void print_bin_coord_hist_data(std::ostream &os, bool normal=true) */
418 /* { */
419
420 /* unsigned i; */
421 /* double tmp; */
422
423 /* // Not very elegant to change this for os - should be changed */
424
425 /* os.setf(std::ios::fixed); */
426 /* os.precision(6); */
427
428 /* if (!discrete_data) */
429 /* { */
430 /* for (i=0; i<bins; ++i) */
431 /* { */
432 /* if (normal) */
433 /* tmp = (double) data[i]/entries/step; */
434 /* else */
435 /* tmp = (double) data[i]; */
436 /* os << (a+(i+0.5)*step) << "\t"; */
437 /* os << tmp << std::endl; */
438 /* } */
439 /* } */
440 /* else */
441 /* { */
442 /* std::map<double, unsigned>::iterator it_beg, it_end; */
443
444 /* it_beg = discrete_hist_data.begin(); */
445 /* it_end = discrete_hist_data.end(); */
446
447 /* while (it_beg != it_end) */
448 /* { */
449 /* if (normal) */
450 /* tmp = (double) it_beg->second/entries/step; */
451 /* else */
452 /* tmp = (double) it_beg->second; */
453 /* os << it_beg->first << "\t" << it_beg->second << std::endl; */
454
455 /* ++it_beg; */
456 /* } */
457 /* } */
458 /* } */
459
460
461 // Returns false if out of range error, else true.
462 bool add(double x)
463 {
464 if (discrete_data)
465 {
466 add_intern_discrete_no_update(x);
467 update_a_b_bins_discrete_data();
468 return true; // Can never fail
469 }
470 else
471 {
472 return add_intern_non_discrete(x);
473 }
474 }
475
476 bool add(std::vector<double> v)
477 {
478 int i, n=v.size();
479
480 if (!discrete_data) // Non-discrete data:
481 {
482 for (i=0; i<n; ++i)
483 if (!add_intern_non_discrete(v[i]))
484 return false;
485 }
486 else // discrete data:
487 {
488 for (i=0; i<n; ++i)
489 {
490 add_intern_discrete_no_update(v[i]);
491 }
492 update_a_b_bins_discrete_data();
493 }
494 return true;
495 }
496
497 template<typename T> // T is some iterator or pointer type
498 bool add(T b, T e) // defines range
499 {
500 if (!discrete_data) // Discrete data:
501 {
502 while (b != e)
503 {
504 if (!add_intern_non_discrete(*b))
505 return false;
506 ++b;
507 }
508 }
509 else
510 {
511 while (b != e)
512 {
513 add_intern_discrete_no_update(*b);
514 ++b;
515 }
516 update_a_b_bins_discrete_data();
517 }
518 return true;
519 }
520
521 bool is_discrete_data()
522 {
523 return discrete_data;
524 }
525
526 unsigned num_entries()
527 {
528 return entries;
529 }
530
531 //XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
532 // old code - needs revision.
533 /* bool get_dominant_category_and_num(double &cat, unsigned &num) */
534 /* { */
535 /* if (discrete_data) */
536 /* { */
537 /* std::map<double, unsigned>::iterator it_beg, it_end; */
538
539 /* it_beg = discrete_hist_data.begin(); */
540 /* it_end = discrete_hist_data.end(); */
541
542 /* if (it_beg == it_end) */
543 /* { */
544 /* return false; */
545 /* } */
546
547 /* cat = it_beg->first; */
548 /* num = it_beg->second; */
549
550 /* while (it_beg != it_end) */
551 /* { */
552 /* if (it_beg->second > num) */
553 /* { */
554 /* cat = it_beg->first; */
555 /* num = it_beg->second; */
556 /* } */
557 /* ++it_beg; */
558 /* } */
559 /* } */
560 /* else // Non discrete data: */
561 /* { */
562 /* double max_key; */
563 /* unsigned max_value; */
564
565 /* unsigned i, n; */
566
567 /* n = data.size(); */
568 /* i = 0; */
569
570 /* if (n == 0) */
571 /* { */
572 /* return false; */
573 /* } */
574
575 /* max_key = a + step/2; */
576 /* max_value = data[0]; */
577
578 /* while (i != n) */
579 /* { */
580 /* if (data[i] > num) */
581 /* { */
582 /* max_key = a + (i + 0.5)*step; */
583 /* max_value = data[i]; */
584 /* } */
585 /* ++i; */
586 /* } */
587 /* } */
588 /* return true; */
589 /* } */
590
591 /* // Should be tested before it is used. */
592 /* void dominant_category(double &value, double &prop) */
593 /* { */
594 /* double cat; */
595 /* unsigned num; */
596
597 /* if (get_dominant_category_and_num(cat, num)) */
598 /* { */
599 /* value = cat; */
600 /* prop = (double)num/entries; */
601 /* } */
602 /* else */
603 /* { */
604 /* value = 0; */
605 /* prop = -1; */
606 /* } */
607 /* } */
608
609
610
611 void categories_sorted_by_dominance(std::vector<std::pair<double, unsigned> > &cat_val_pair_vec)
612 {
613 if (discrete_data)
614 {
615 std::map<double, unsigned>::iterator it_beg, it_end;
616
617 it_beg = discrete_hist_data.begin();
618 it_end = discrete_hist_data.end();
619
620 if (it_beg == it_end)
621 {
622 return;
623 }
624
625 while (it_beg != it_end)
626 {
627 double cat;
628 unsigned num;
629
630 cat = it_beg->first;
631 num = it_beg->second;
632
633 cat_val_pair_vec.push_back(std::make_pair(cat, num));
634
635 ++it_beg;
636 }
637 }
638 else // Non discrete data:
639 {
640 double key;
641 unsigned value;
642
643 unsigned i, n;
644
645 n = data.size();
646 i = 0;
647
648 if (n == 0)
649 {
650 return;
651 }
652
653 while (i != n)
654 {
655 key = a + step/2;
656 value = data[0];
657
658 cat_val_pair_vec.push_back(std::make_pair(key, value));
659 ++i;
660 }
661 }
662
663 sort(cat_val_pair_vec.begin(), cat_val_pair_vec.end(), greater_than_pair);
664 }
665
666 };
667
668 #endif