Debian Codegraph @

range_functions.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 RANGE_FUNCTIONS_H
29 #define RANGE_FUNCTIONS_H
30
31 #include <iostream>
32 #include <list>
33 #include <cstdlib>
34 #include "faststring2.h"
35 #include <cerrno>
36 #include <iterator>
37 #include <vector>
38
39 #define MACRO_MAX(x,y) ((x)<(y) ? (y) : (x))
40 #define MACRO_MIN(x,y) ((x)<(y) ? (x) : (y))
41
42 // This is a range class for unsigned numbers not for double numbers, which would
43 // be interesting in its own right.
44 // In principle one could make a template class out of this.
45
46
47 //
48 // General conventions:
49 // - ranges are undirected
50 // - start <= end
51 // - end is position after last position in range
52 // - ranges can be 0 or 1 based. Be careful!!!!
53 // - the preferred way to represent a vanishing range is (0,0).
54 // TODO: See comments in functions for which this convention does not apply.
55 // TODO: Several functions work independent of a convention here.
56 //
57
58
59
60
61 class CRangeList;
62
63 class Crange
64 {
65
66 friend class CRangeList;
67
68 unsigned b;
69 unsigned e;
70
71 public:
72
73 Crange(unsigned pb, unsigned pe):b(pb), e(pe)
74 {
75 order();
76 }
77
78 void order() // According to the conventions above: b <= e
79 {
80 if (b > e)
81 {
82 unsigned tmp = b;
83 b = e;
84 e = tmp;
85 }
86 }
87
88
89 friend unsigned overlap(Crange r1, Crange r2)
90 {
91 unsigned overlap_start = MACRO_MAX(r1.b, r2.b);
92 unsigned overlap_end = MACRO_MIN(r1.e, r2.e);
93
94 if (overlap_end > overlap_start)
95 return overlap_end - overlap_start;
96 else
97 return 0;
98 }
99
100 friend Crange overlap_range(Crange r1, Crange r2)
101 {
102 unsigned overlap_start = MACRO_MAX(r1.b, r2.b);
103 unsigned overlap_end = MACRO_MIN(r1.e, r2.e);
104
105 if (overlap_end > overlap_start)
106 {
107 Crange res(overlap_start, overlap_end);
108 return res;
109 }
110 else
111 return Crange(0,0);
112 }
113
114 friend void overlap_range(Crange r1, Crange r2, Crange &res1, Crange &res_over, Crange &res2)
115 {
116 unsigned overlap_start = MACRO_MAX(r1.b, r2.b);
117 unsigned overlap_end = MACRO_MIN(r1.e, r2.e);
118 unsigned res1_start = MACRO_MIN(r1.b, r2.b);
119 unsigned res2_end = MACRO_MAX(r1.e, r2.e);
120
121 if (overlap_end > overlap_start)
122 {
123 res_over.assign(overlap_start, overlap_end);
124 res1.assign(res1_start, overlap_start);
125 res2.assign(overlap_end, res2_end);
126 }
127 else
128 {
129 res_over.assign(0, 0);
130 if (r1 < r2)
131 {
132 res1 = r1;
133 res2 = r2;
134 }
135 else
136 {
137 res1 = r2;
138 res2 = r1;
139 }
140 }
141 }
142
143 friend double overlap_proportion(Crange r1, Crange r2)
144 {
145 unsigned overlap_start = MACRO_MAX(r1.b, r2.b);
146 unsigned overlap_end = MACRO_MIN(r1.e, r2.e);
147
148 if (overlap_end > overlap_start)
149 {
150 double overl = overlap_end - overlap_start;
151 double l = MACRO_MIN(r1.len(), r2.len());
152
153 return (overl/l);
154 }
155 else
156 return 0.0;
157 }
158
159
160 friend bool adjacent_or_overlap(Crange r1, Crange r2)
161 {
162 unsigned overlap_start = MACRO_MAX(r1.b, r2.b);
163 unsigned overlap_end = MACRO_MIN(r1.e, r2.e);
164
165 if (overlap_end >= overlap_start)
166 return true; // == means they are adjacent
167 else
168 return false;
169 }
170
171 Crange()
172 {
173 b = e = 0;
174 }
175
176 friend void swap(Crange &r1, Crange &r2)
177 {
178 Crange tmp = r2;
179 r2 = r1;
180 r1 = tmp;
181 }
182
183 friend void swap(Crange *r1, Crange *r2)
184 {
185 Crange tmp = *r2;
186 *r2 = *r1;
187 *r1 = tmp;
188 }
189
190 bool empty() const
191 {
192 return (b == e);
193 }
194
195 void limit_to_range(Crange limit_r)
196 {
197 // Nothing to be done in this case:
198 if (is_r2_Subrange_of_r1(limit_r, *this) )
199 return;
200
201 b = MACRO_MAX(limit_r.b, b);
202 e = MACRO_MIN(limit_r.e, e);
203 if (b >= e)
204 b = e = 0;
205 }
206
207 friend bool operator==(Crange r1, Crange r2)
208 {
209 return (r1.b == r2.b && r1.e == r2.e);
210 }
211
212 void assign(unsigned pb, unsigned pe)
213 {
214 b = pb;
215 e = pe;
216 order();
217 }
218
219 // true if r1 starts before r2
220 // true if r1 starts with r2 and if r1 is shorter
221 // r1 *******
222 // r2 *********** r1 < r2 is true
223 friend bool operator<(Crange r1, Crange r2)
224 {
225 if (r1.b != r2.b)
226 return r1.b < r2.b;
227 return r1.e < r2.e;
228 }
229
230 friend bool equalRange(Crange r1, Crange r2)
231 {
232 return (r1 == r2);
233 }
234
235
236 friend bool is_r2_Subrange_of_r1(Crange r1, Crange r2)
237 {
238 return (r2.b >= r1.b && r2.e <= r1.e);
239 }
240
241 friend Crange range_intersection(Crange r1, Crange r2)
242 {
243 Crange res( MACRO_MAX(r1.b,r2.b), MACRO_MIN(r1.e,r2.e));
244 if (res.b >= res.e)
245 res.e = res.b = 0;
246
247 return res;
248 }
249
250 friend bool before(Crange r1, Crange r2)
251 {
252 return r1.e <= r2.b;
253 }
254
255 friend bool after(Crange r1, Crange r2)
256 {
257 return r1.b >= r2.e;
258 }
259
260 // formerly called range_union, which was a misnomer.
261 // friend ......
262
263 friend Crange range_span(Crange r1, Crange r2)
264 {
265 Crange res( MACRO_MIN(r1.b,r2.b), MACRO_MAX(r1.e,r2.e));
266 return res;
267 }
268
269
270 void shift (unsigned s)
271 {
272 b +=s;
273 e +=s;
274 }
275
276 unsigned begin() const
277 {
278 return b;
279 }
280
281 unsigned end() const
282 {
283 return e;
284 }
285
286 unsigned inclusive_end() const
287 {
288 return e-1;
289 }
290
291 unsigned len() const
292 {
293 return e-b;
294 }
295
296 bool point_is_in_range(unsigned x) const
297 {
298 if (x>=b && x < e)
299 return true;
300 else
301 return false;
302 }
303
304 bool point_is_behind_range(unsigned x) const
305 {
306 if (x >= e)
307 return true;
308 else
309 return false;
310 }
311
312 bool point_is_before_range(unsigned x) const
313 {
314 if (x < b)
315 return true;
316 else
317 return false;
318 }
319
320 void print_with_brackets(std::ostream &os) const
321 {
322 os << "(" << b << "," << e << ")";
323 }
324
325 void print_with_brackets_inclusive_end(std::ostream &os) const
326 {
327 os << "(" << b << "," << (e-1) << ")";
328 }
329
330 void print_minus_deliminated_inclusive_end(std::ostream &os) const
331 {
332 os << b << "-" << (e-1);
333 }
334
335 void transform_start_end(int mult_start, int add_start, int mult_end, int add_end)
336 {
337 b = b*mult_start + add_start;
338 e = e*mult_end + add_end;
339 }
340
341 void transform_coord(std::vector<unsigned> &coord_trans)
342 {
343 // We subtract 1 from e before we look up this index in the field, since the end index of a range is 1 behind its last element.
344 if ( e-1 >= coord_trans.size() )
345 {
346 std::cerr << "Index out of range: " << e << std::endl;
347 exit(-33);
348 }
349
350 b = coord_trans[b];
351 e = coord_trans[e-1]+1; // We transform the coord of the last element and add 1.
352 }
353
354
355 }; // class Crange
356
357
358
359
360 /* class CRangeList_array */
361 /* { */
362 /* Crange limit; */
363 /* faststring rl_array; */
364
365 /* CRangeList_array(Crang l):limit(l), faststring('\0', l.end()-l.begin()+1) */
366 /* {} */
367
368 /* Crange get_limit() */
369 /* { */
370 /* return limit; */
371 /* } */
372
373 /* unsigned get_limit_begin() */
374 /* { */
375 /* return limit.begin(); */
376 /* } */
377
378 /* unsigned get_limit_end() */
379 /* { */
380 /* return limit.end(); */
381 /* } */
382
383
384
385 /* }; */
386
387
388
389
390 // NOTE: Code referring to array is either experimental or unfinished.
391 //
392 //
393
394 class CRangeList
395 {
396 std::list<Crange> rl;
397 bool sorted;
398 unsigned lower_bound;
399 unsigned upper_bound; // According to the convention this position comes after the last position in this list of ranges.
400 unsigned count; // Introduced since the empty() function could be
401 // via size()==0, whereas size could be O(n)
402 // which might be very inefficient.
403 // rl_array is not fully implemented: In the future it could be used to store "in" and "out of" the range list
404 // by setting chars to 1 or 0, which would make many functions more efficient.
405 faststring *rl_array;
406
407
408 public:
409 typedef std::list<Crange>::iterator CRangeList_iterator;
410 typedef std::list<Crange>::const_iterator CRangeList_iterator_const;
411
412 // Default constructor:
413 // Caution: lower_bound and upper_bound are set to 0, since they are needed by
414 // some functions. This is better than arbitrary values.
415 // even though one could say the values are not correct.
416 // But arbitrary values are not more correct than 0.
417 // Take care that all member functions set these variables
418 // if the first element of a list is added.
419
420 CRangeList():sorted(false), lower_bound(0), upper_bound(0), count(0), rl_array(NULL)
421 {}
422
423 // Copy constructor
424 CRangeList(const CRangeList &a):rl(a.rl), lower_bound(a.lower_bound), upper_bound(a.upper_bound), count(a.count), rl_array(NULL)
425 {
426 if (a.rl_array != NULL)
427 {
428 rl_array = new faststring(*a.rl_array);
429 }
430 }
431
432 void clear_rl_array()
433 {
434 if (rl_array)
435 {
436 delete rl_array;
437 rl_array = NULL;
438 }
439 }
440
441 ~CRangeList()
442 {
443 clear_rl_array();
444 }
445
446
447 public:
448 void add(unsigned pb, unsigned pe)
449 {
450 Crange new_r (pb, pe);
451
452 if (new_r.empty())
453 return;
454
455 clear_rl_array();
456
457 // If the new element is > than the last element in the list,
458 // sorting is not affected, otherwise "it is false".
459 // Note: We cannot set sorted to true, if the rest of the list is not sorted.
460
461 if (count == 0)
462 {
463 sorted = true;
464 lower_bound = new_r.b;
465 upper_bound = new_r.e;
466 rl.push_back(new_r);
467 }
468 else
469 {
470 if ( !(rl.back() < new_r) )
471 sorted = false;
472 // else - do not change sorted status
473
474 if (lower_bound > new_r.b)
475 lower_bound = new_r.b;
476 if (upper_bound < new_r.e)
477 upper_bound = new_r.e;
478
479 rl.push_back(new_r);
480 }
481 ++count;
482 }
483
484 CRangeList_iterator_const begin() const
485 {
486 return rl.begin();
487 }
488
489 CRangeList_iterator_const begin()
490 {
491 return rl.begin();
492 }
493
494 CRangeList_iterator_const end() const
495 {
496 return rl.end();
497 }
498
499 CRangeList_iterator_const end()
500 {
501 return rl.end();
502 }
503
504 // Test before using this function
505 void create_reset_rl_array()
506 {
507 if (rl_array)
508 {
509 rl_array->assign(upper_bound-lower_bound, '\0');
510 }
511 else
512 {
513 rl_array = new faststring('\0', upper_bound-lower_bound);
514 }
515 }
516
517 // Test before using this function
518 void fill_rl_array()
519 {
520 if (rl_array == NULL)
521 create_reset_rl_array();
522
523 CRangeList_iterator_const it = rl.begin();
524 CRangeList_iterator_const it_end = rl.end();
525
526 unsigned pos1, pos2;
527
528 // foreach range:
529 while (it != it_end)
530 {
531 pos1 = it->begin();
532 pos2 = it->end();
533
534 while (pos1 < pos2)
535 {
536 rl_array[pos1] = 1;
537 ++pos1;
538 }
539 ++it;
540 }
541 }
542
543 void add(Crange new_r)
544 {
545 // If the new element is > than the last element in the list,
546 // sorting is not affected, otherwise "it is false".
547 // Note: We cannot set sorted to true, if the rest of the list is not sorted.
548
549 clear_rl_array();
550
551 if (new_r.empty())
552 return;
553
554 if (count == 0)
555 {
556 sorted = true;
557 lower_bound = new_r.b;
558 upper_bound = new_r.e;
559 rl.push_back(new_r);
560 }
561 else
562 {
563 if ( !(rl.back() < new_r) )
564 sorted = false;
565 // else - do not change sorted status
566
567 if (lower_bound > new_r.b)
568 lower_bound = new_r.b;
569 if (upper_bound < new_r.e)
570 upper_bound = new_r.e;
571
572 rl.push_back(new_r);
573 }
574 ++count;
575 }
576
577
578 void add(const CRangeList &a)
579 {
580 CRangeList_iterator_const it = a.rl.begin();
581 CRangeList_iterator_const it_end = a.rl.end();
582
583 while (it != it_end)
584 {
585 if ( !it->empty() )
586 add(*it);
587 ++it;
588 }
589 }
590
591 bool add(faststring str)
592 {
593 faststring::size_t pos1=0, pos2, len=str.size();
594 unsigned c1,c2;
595
596 while (pos1 < len && str[pos1] != ';')
597 {
598 str.skip_symbol(pos1,' ');
599
600 errno = 0;
601 c1 = str.ToUnsigned(pos1, pos2);
602 // std::cerr << "c1 " << c1 << std::endl;
603 if (errno != 0)
604 {
605 return false;
606 }
607 str.skip_symbol(pos2,' ');
608
609 if (str[pos2] == ',' || str[pos2] == ';') // One number range.
610 {
611 add(c1,c1+1);
612 }
613 else if (str[pos2] == '-') // Two number range
614 {
615 pos1 = pos2+1; // Be careful '-' is read as minus
616 str.skip_symbol(pos1,' ');
617 // std::cerr << "pos1 " << pos1 << std::endl;
618 errno = 0;
619 c2 = str.ToUnsigned(pos1, pos2);
620 // std::cerr << "c2 " << c2 << std::endl;
621 if (errno != 0)
622 {
623 return false;
624 }
625 // std::cerr << "pos2 " << pos2 << std::endl;
626 str.skip_symbol(pos2,' ');
627 if (str[pos2] > '\0' && str[pos2] <= '\7')
628 {
629 unsigned tmp = c1;
630 unsigned delta = str[pos2]-'\0';
631 if (errno != 0)
632 {
633 return false;
634 }
635 ++pos2;
636 str.skip_symbol(pos2,' ');
637
638 while (tmp < c2)
639 {
640 add(tmp, tmp+1);
641 tmp += delta;
642 }
643 }
644 else
645 {
646 add(c1, c2+1);
647 }
648 }
649 else
650 {
651 return false;
652 }
653 pos1 = pos2;
654
655 if (str[pos1] == ',') // we are not done yet - the list continues
656 {
657 ++pos1;
658 str.skip_symbol(pos1,' ');
659 if (str[pos1] == ';')
660
661 return false;
662 }
663 }
664 return true;
665 }
666
667
668 bool add_delta(faststring str)
669 {
670 faststring::size_t pos1=0, pos2, len=str.size();
671 unsigned c1,c2;
672
673 while (pos1 < len && str[pos1] != ';')
674 {
675 str.skip_symbol(pos1,' ');
676
677 errno = 0;
678 c1 = str.ToUnsigned(pos1, pos2);
679 // std::cerr << "c1 " << c1 << std::endl;
680 if (errno != 0)
681 {
682 return false;
683 }
684 str.skip_symbol(pos2,' ');
685
686 if (str[pos2] == ',' || str[pos2] == ';') // One number range.
687 {
688 add(c1,c1+1);
689 }
690 else if (str[pos2] == '-') // Two number range
691 {
692 pos1 = pos2+1; // Be careful '-' is read as minus
693 str.skip_symbol(pos1,' ');
694 // std::cerr << "pos1 " << pos1 << std::endl;
695 errno = 0;
696 c2 = str.ToUnsigned(pos1, pos2);
697 // std::cerr << "c2 " << c2 << std::endl;
698 if (errno != 0)
699 {
700 return false;
701 }
702 // std::cerr << "pos2 " << pos2 << std::endl;
703 str.skip_symbol(pos2,' ');
704 if (str[pos2] == '\\')
705 {
706 ++pos2;
707 str.skip_symbol(pos2,' ');
708
709 char d = str[pos2];
710 unsigned tmp = c1;
711 unsigned delta = d-'0';
712 if (errno != 0)
713 {
714 return false;
715 }
716 ++pos2;
717 str.skip_symbol(pos2,' ');
718
719 while (tmp < c2)
720 {
721 add(tmp, tmp+1);
722 tmp += delta;
723 }
724 }
725 else
726 {
727 add(c1, c2+1);
728 }
729 }
730 else
731 {
732 return false;
733 }
734 pos1 = pos2;
735
736 if (str[pos1] == ',') // we are not done yet - the list continues
737 {
738 ++pos1;
739 str.skip_symbol(pos1,' ');
740 if (str[pos1] == ';')
741
742 return false;
743 }
744 }
745 return true;
746 }
747
748
749 unsigned size() const
750 {
751 return count;
752 }
753
754 // Assignment operator: Use standard assignment operator. No pointer content needs to be copied
755 // This is still true since rl_array is not ready to use yet.
756 // Currently there is no need/no plan to implement it.
757
758 void clear()
759 {
760 rl.clear(); // Will call the destructor for all objects.
761 sorted = false;
762 clear_rl_array();
763 // I am not sure this is the best way to assign values to the bounds.
764 // Bounds are not well defined for an empty list.
765 lower_bound = upper_bound = 0;
766 count = 0;
767 }
768
769
770 void sort()
771 {
772 if (!sorted)
773 {
774 rl.sort();
775 sorted = true;
776 }
777 }
778
779
780 // We expect the use to check for count == 0
781 Crange bounds()
782 {
783 // There is one problem here: The last entry need to have the "highest coordinate"
784 // 100-150, 200-400, 250-300
785
786 Crange res(lower_bound, upper_bound);
787 return res;
788 }
789
790 // We expect the use to check for count == 0
791 unsigned get_lower_bound()
792 {
793 return lower_bound;
794 }
795
796 // We expect the use to check for count == 0
797 unsigned get_upper_bound()
798 {
799 return upper_bound;
800 }
801
802
803 // Find an island of overlapping ranges, starting at it_beg.
804 // The initial value of it_end (the second parameter) is overwritten,
805 // and is therefore irrelevant.
806 // When leaving this function, it_end points to the range behind the island.
807 // This is also true, if the island is the last island in the list.
808 // In this case, it_end == to list_of_sat_ptr.end()
809
810 unsigned findOverlappingIsland(CRangeList_iterator_const it_beg,
811 CRangeList_iterator_const &it_end) const
812 {
813 unsigned count=1;
814
815 it_end = it_beg;
816 ++it_end;
817
818 while (it_end != rl.end())
819 {
820 if (overlap(*it_beg, *it_end)) // If they overlap, we move it_end,
821 {
822 ++count;
823 ++it_end;
824 }
825 else // if they do not overlap any more, we need not be out of the island.
826 { // Let us move it_beg, which should now be behind or equal to it_end.
827 ++it_beg;
828 if (it_beg == it_end) // this is the case of the last two sats do not overlap
829 break; // In this case it_end points one behind the last island.
830 }
831 }
832 return count;
833 }
834
835 unsigned findAdjacentIsland(CRangeList_iterator_const it_beg,
836 CRangeList_iterator_const &it_end) const
837 {
838 unsigned count=1; // The current range is the Nr 1.
839
840 it_end = it_beg;
841 ++it_end;
842
843 while (it_end != rl.end())
844 {
845 if (adjacent_or_overlap(*it_beg, *it_end)) // If they overlap, we move it_end,
846 {
847 ++count;
848 ++it_end;
849 }
850 else // if they do not overlap any more, we need not be out of the island.
851 { // Let us move it_beg, which should now be behind or equal to it_end.
852 ++it_beg;
853 if (it_beg == it_end) // this is the case of the last two sats do not overlap
854 break; // In this case it_end points one behind the last island.
855 }
856 }
857 return count;
858 }
859
860
861 void findRangeWithMaxExtToRight(CRangeList_iterator_const it_beg,
862 CRangeList_iterator_const it_end,
863 CRangeList_iterator_const &it_extends_most) const
864 {
865 it_extends_most = it_beg;
866 if (it_beg == it_end)
867 return;
868
869 ++it_beg;
870 while (it_beg != it_end)
871 {
872 if ((*it_beg).e > (*it_extends_most).e )
873 it_extends_most = it_beg;
874 ++it_beg;
875 }
876 }
877
878
879 Crange range_of_island(CRangeList_iterator_const it_beg,
880 CRangeList_iterator_const &it_end_of_island)
881 {
882 Crange res;
883 CRangeList_iterator_const it_extends_most;
884
885 if (!sorted)
886 {
887 std::cerr << "Error: range_of_island requires the list of ranges to be sorted." << std::endl;
888 exit(0);
889 }
890
891 res.b = it_beg->b;
892
893 findOverlappingIsland(it_beg, it_end_of_island);
894 findRangeWithMaxExtToRight(it_beg, it_end_of_island, it_extends_most);
895
896 res.e = it_extends_most->e;
897
898 return res;
899 }
900
901 Crange range_of_adjacentisland(CRangeList_iterator_const it_beg,
902 CRangeList_iterator_const &it_end_of_island)
903 {
904 Crange res;
905 CRangeList_iterator_const it_extends_most;
906
907 if (!sorted)
908 {
909 std::cerr << "Internal error: range_of_adjacentisland requires the list of ranges to be sorted." << std::endl;
910 exit(0);
911 }
912
913 res.b = it_beg->b;
914
915 findAdjacentIsland(it_beg, it_end_of_island);
916 findRangeWithMaxExtToRight(it_beg, it_end_of_island, it_extends_most);
917
918 res.e = it_extends_most->e;
919
920 return res;
921 }
922
923
924 // coverage_len allows us to specify a range - double check that feature.
925 double coverage_rel(Crange bds)
926 {
927 CRangeList rl_tmp(*this);
928
929 rl_tmp.limit_to_range(bds);
930
931 double bds_len = bds.len();
932
933 return rl_tmp.coverage_len(bds)/bds_len;
934 }
935
936 unsigned coverage_len2(Crange bds)
937 {
938 CRangeList rl2;
939 get_consolidated_range_list(rl2);
940
941 rl2.limit_to_range(bds);
942 return rl2.coverage_raw();
943 }
944
945 unsigned coverage_raw()
946 {
947 unsigned lencount=0;
948
949 CRangeList_iterator_const it, it_end;
950
951 it = rl.begin();
952 it_end = rl.end();
953
954 while (it != it_end)
955 {
956 lencount += it->len();
957 ++it;
958 }
959 return lencount;
960 }
961
962 // Side effect: *this will be sorted
963 unsigned coverage_len(Crange bds) // bounds in which to compute the coverage
964 {
965 unsigned cover = 0;
966
967 CRangeList_iterator_const it, it_end, end_island;
968 Crange r1, r2;
969
970 // std::cerr << "Computing coverage for this: " << std::endl;
971 // print_bracketed_list(std::cerr);
972 // std::cerr << std::endl;
973
974 sort();
975
976 it = rl.begin();
977 it_end = rl.end();
978
979 while (it != it_end && it->e < bds.b)
980 ++it;
981
982 if (it == it_end)
983 return 0;
984
985 // it points to first range after start of bds
986 r1 = range_of_island(it, end_island);
987 cover += overlap(r1, bds);
988 it = end_island;
989 // std::cerr << "First overlap: " << cover << std::endl;
990
991 while (it != it_end && it->b < bds.e)
992 {
993 r1 = range_of_island(it, end_island);
994 it = end_island;
995 if (r1.e > bds.e)
996 {
997 cover += overlap(r1, bds);
998 break;
999 }
1000 else
1001 cover += r1.len();
1002 // std::cerr << "next value: " << cover << std::endl;
1003 }
1004
1005 return cover;
1006 }
1007
1008 // Side effect: *this will be sorted
1009 unsigned coverage_len() // without bounds
1010 {
1011 unsigned cover = 0;
1012
1013 CRangeList_iterator_const it, it_end, end_island;
1014 Crange r1;
1015
1016 // std::cerr << "Computing coverage for this: " << std::endl;
1017 // print_bracketed_list(std::cerr);
1018 // std::cerr << std::endl;
1019
1020 sort();
1021
1022 it = rl.begin();
1023 it_end = rl.end();
1024
1025 while (it != it_end)
1026 {
1027 r1 = range_of_island(it, end_island);
1028 it = end_island;
1029
1030 cover += r1.len();
1031 // std::cerr << "next value: " << cover << std::endl;
1032 }
1033
1034 return cover;
1035 }
1036
1037 unsigned coverage_len_loop() // without bounds
1038 {
1039 unsigned cover = 0;
1040 Crange r1, b;
1041
1042 // std::cerr << "Computing coverage for this: " << std::endl;
1043 // print_bracketed_list(std::cerr);
1044 // std::cerr << std::endl;
1045
1046 if (count == 0)
1047 return 0;
1048
1049 // Required by point_is_in_RangeList
1050 sort();
1051
1052 CRangeList_iterator_const it1 = rl.begin();
1053
1054 b = bounds(); //Upper bound of this range is element after range.
1055 unsigned i, b_end;
1056
1057 b_end = b.end();
1058 for (i=b.begin(); i<b_end; ++i)
1059 {
1060 if (point_is_in_RangeList(i, it1) )
1061 {
1062 ++cover;
1063 }
1064 }
1065 return cover;
1066 }
1067
1068
1069
1070 void test1()
1071 {
1072 CRangeList_iterator_const it1 = rl.begin();
1073 CRangeList_iterator_const it2 = rl.end();
1074 CRangeList_iterator_const it3, it4;
1075
1076 while (it1 != it2)
1077 {
1078 Crange r = range_of_island(it1, it3);
1079
1080 it1 = it3;
1081
1082 std::cout << "Next range: " << std::endl;
1083 r.print_with_brackets(std::cout);
1084 std::cout << std::endl;
1085 }
1086 }
1087
1088 void print_bracketed_list(std::ostream &os) const
1089 {
1090 CRangeList_iterator_const it_beg = rl.begin();
1091 CRangeList_iterator_const it_end = rl.end();
1092
1093 if (it_beg == it_end)
1094 return;
1095
1096 while (1) //(it_beg != it_end)
1097 {
1098 it_beg->print_with_brackets(os);
1099 ++it_beg;
1100 if (it_beg == it_end)
1101 return;
1102 os << ",";
1103 }
1104 }
1105
1106 void print_bracketed_list_inclusive_ends(std::ostream &os) const
1107 {
1108 CRangeList_iterator_const it_beg = rl.begin();
1109 CRangeList_iterator_const it_end = rl.end();
1110
1111 if (it_beg == it_end)
1112 return;
1113
1114 while (1) //(it_beg != it_end)
1115 {
1116 it_beg->print_with_brackets_inclusive_end(os);
1117 ++it_beg;
1118 if (it_beg == it_end)
1119 return;
1120 os << ",";
1121 }
1122 }
1123
1124
1125 void print_deliminated_inclusive_end(std::ostream &os, const char *delim) const
1126 {
1127 CRangeList_iterator_const it_beg = rl.begin();
1128 CRangeList_iterator_const it_end = rl.end();
1129
1130 if (it_beg == it_end)
1131 return;
1132
1133 while (1) //(it_beg != it_end)
1134 {
1135 it_beg->print_minus_deliminated_inclusive_end(os);
1136 ++it_beg;
1137 if (it_beg == it_end)
1138 return;
1139 os << delim;
1140 }
1141 }
1142
1143 void print_deliminated_inclusive_end(std::ostream &os, char delim= ',') const
1144 {
1145 CRangeList_iterator_const it_beg = rl.begin();
1146 CRangeList_iterator_const it_end = rl.end();
1147
1148 if (it_beg == it_end)
1149 return;
1150
1151 while (1) //(it_beg != it_end)
1152 {
1153 it_beg->print_minus_deliminated_inclusive_end(os);
1154 ++it_beg;
1155 if (it_beg == it_end)
1156 return;
1157 os << delim;
1158 }
1159 }
1160
1161
1162 // For this CRangeList compute a consolidated range list:
1163 // Adjacent or overlapping ranges are merged in the consolidated list
1164 void get_consolidated_range_list(CRangeList &crl)
1165 {
1166 sort();
1167 crl.clear();
1168
1169 CRangeList_iterator_const it1, it2;
1170
1171 it1 = it2 = rl.begin();
1172
1173 while (it2 != rl.end() )
1174 {
1175 crl.add(range_of_adjacentisland(it1, it2) );
1176 // crl.sort();
1177 it1 = it2;
1178 }
1179 }
1180
1181
1182 void remove_empty() // Now we try to avoid to add empty ranges in the first place
1183 {
1184 CRangeList_iterator it1;
1185
1186 it1 = rl.begin();
1187
1188 while (it1 != rl.end() )
1189 {
1190 if ( it1->empty() )
1191 {
1192 it1 = rl.erase(it1);
1193 --count;
1194 }
1195 else
1196 ++it1;
1197 }
1198 }
1199
1200
1201 // Side effect: Removes empty ranges form list:
1202 void limit_to_range(Crange limit_r)
1203 {
1204 CRangeList_iterator it1;
1205
1206 clear_rl_array();
1207
1208 it1 = rl.begin();
1209
1210 if (sorted)
1211 {
1212 // std::cout << "sorted mode" << std::endl;
1213 while (it1 != rl.end() && before(*it1, limit_r) )
1214 {
1215 // remove ranges before limiting range:
1216 ++it1;
1217 }
1218 if (it1 != rl.begin())
1219 rl.erase(rl.begin(), it1);
1220 // count will be reset at the end!!
1221
1222 while (it1 != rl.end() && !after(*it1, limit_r) )
1223 {
1224 it1->limit_to_range(limit_r);
1225
1226 if ( it1->empty() )
1227 {
1228 it1 = rl.erase(it1);
1229 // count will be reset at the end!!
1230 }
1231 else
1232 ++it1;
1233 }
1234
1235 if (it1 != rl.end() )
1236 {
1237 // remove ranges after limiting range:
1238 rl.erase(it1, rl.end());
1239 // count will be reset at the end!!
1240 }
1241 }
1242 else
1243 {
1244 while (it1 != rl.end() )
1245 {
1246 it1->limit_to_range(limit_r);
1247
1248 if ( it1->empty() )
1249 {
1250 it1 = rl.erase(it1);
1251 // count will be reset at the end!!
1252 }
1253 else
1254 ++it1;
1255 }
1256 }
1257 // This could be made a bit more efficient.
1258 // This solution however is most secure.
1259 count = rl.size();
1260 }
1261
1262
1263 friend CRangeList range_union(Crange a, Crange b)
1264 {
1265 CRangeList tmp, res;
1266
1267 tmp.add(a);
1268 tmp.add(b);
1269
1270 tmp.get_consolidated_range_list(res);
1271
1272 return res;
1273 }
1274
1275 friend CRangeList cut_out_range(Crange a, Crange b)
1276 {
1277 Crange r1, r2, r3;
1278 CRangeList res;
1279
1280 overlap_range(a,b,r1, r2, r3);
1281
1282 res.add(r1);
1283 res.add(r3);
1284 return res;
1285 }
1286
1287
1288 void set_to_range_list_union(const CRangeList &a, const CRangeList &b)
1289 {
1290 CRangeList tmp(a);
1291 tmp.add(b);
1292
1293 clear();
1294 tmp.get_consolidated_range_list(*this);
1295 }
1296
1297 void set_to_range_list_intersection(CRangeList &a, CRangeList &b)
1298 {
1299 clear();
1300
1301 CRangeList ca, cb;
1302
1303 a.get_consolidated_range_list(ca);
1304 b.get_consolidated_range_list(cb);
1305
1306 CRangeList_iterator_const it_a, it_b;
1307
1308 it_a = ca.rl.begin();
1309 it_b = cb.rl.begin();
1310
1311 while (it_a != ca.rl.end() )
1312 {
1313 // While the range it_b lies before it_a:
1314 while ( it_b != cb.rl.end() && before(*it_b, *it_a) )
1315 {
1316 ++it_b;
1317 }
1318 // While the range it_a overlaps with it_b:
1319 while ( it_b != cb.rl.end() && overlap(*it_a, *it_b) )
1320 {
1321 add(range_intersection(*it_a, *it_b) );
1322 ++it_b;
1323 }
1324 if (it_b != cb.rl.begin())
1325 --it_b;
1326 ++it_a;
1327 }
1328 }
1329
1330 // Side effect: list of ranges will be sorted
1331 bool point_is_in_RangeList(unsigned x)
1332 {
1333 sort();
1334 CRangeList_iterator_const it1, it2;
1335
1336 it1 = rl.begin();
1337 it2 = rl.end();
1338
1339 // Skip all ranges which have an end value that lies before x
1340 while (it1 != it2 && x >= it1->e)
1341 {
1342 ++it1;
1343 }
1344
1345 // Test all ranges which have a beginning that lies before x
1346 while (it1 != it2 && x >= it1->b)
1347 {
1348 if (it1->point_is_in_range(x))
1349 return true;
1350 ++it1;
1351 }
1352 // All remaining ranges have a beginning that lies behind x:
1353 return false;
1354 }
1355
1356 // Requirement: list of ranges must be sorted
1357 bool point_is_in_RangeList(unsigned x, CRangeList_iterator_const &it1) const
1358 {
1359 if (!sorted)
1360 {
1361 std::cerr << "When calling point_is_in_RangeList, the range list must be sorted." << std::endl;
1362 exit(-11);
1363 }
1364
1365 CRangeList_iterator_const it2;
1366 it2 = rl.end();
1367
1368 // Skip all ranges which have an end value that lies before x
1369 while (it1 != it2 && x >= it1->e)
1370 {
1371 ++it1;
1372 }
1373
1374 // Test all ranges which have a beginning that lies before x
1375 while (it1 != it2 && x >= it1->b)
1376 {
1377 if (it1->point_is_in_range(x))
1378 return true;
1379 ++it1;
1380 }
1381 if (it1 != rl.begin() )
1382 --it1; // We might have moved too far.
1383
1384 // All remaining ranges have a beginning that lies behind x:
1385 return false;
1386 }
1387
1388
1389 void export_as_gff(std::ostream &os, const char *seq, const char* source, const char *type, char direction)
1390 {
1391 CRangeList_iterator_const it = rl.begin();
1392 CRangeList_iterator_const it_end = rl.end();
1393
1394 while (it != it_end)
1395 {
1396 os << seq << "\t"
1397 << source << "\t"
1398 << type << "\t"
1399 << it->b << "\t"
1400 << it->e << "\t"
1401 << ".\t"
1402 << direction << "\t"
1403 << ".\t"
1404 << "ID=" << seq << "_" << it->b << "_" << it->e << std::endl;
1405 ++it;
1406 }
1407 }
1408
1409 // Side effect: CRangeList rl is being sorted and set to a consolidated list.
1410 void set_to_complement_of(CRangeList &rl, Crange limit)
1411 {
1412 CRangeList crl;
1413 Crange r1, r2, r3;
1414
1415 // Clear this CRangeList. Otherwise we add to a probably non empty list.
1416 clear();
1417
1418 rl.get_consolidated_range_list(crl);
1419
1420 crl.sort(); // Should already be sorted. Just to be sure.
1421 crl.limit_to_range(limit);
1422
1423 CRangeList_iterator_const it = crl.rl.begin();
1424 CRangeList_iterator_const it_end = crl.rl.end();
1425
1426 r3 = limit;
1427 while (it != it_end)
1428 {
1429 // r2 is just a dummy for the overlapping part.
1430 overlap_range(r3, *it, r1, r2, r3);
1431 // std::cerr << "Adding "; r1.print_with_brackets(std::cerr); std::cerr << std::endl;
1432 add(r1);
1433 ++it;
1434 }
1435 add(r3);
1436 }
1437
1438
1439 unsigned* get_range_list_field()
1440 {
1441 unsigned* p = new unsigned [2*count];
1442
1443 CRangeList_iterator_const it = rl.begin();
1444 CRangeList_iterator_const it_end = rl.end();
1445 unsigned i=0;
1446
1447 sort();
1448
1449 while (it != it_end)
1450 {
1451 p[i] = it->begin();
1452 p[i+1] = it->end();
1453 ++i;
1454 ++it;
1455 }
1456 return p;
1457 }
1458
1459 friend bool less_than_CRangeList(const CRangeList &a, const CRangeList &b)
1460 {
1461 CRangeList_iterator_const it_a = a.rl.begin();
1462 CRangeList_iterator_const it_b = b.rl.begin();
1463 CRangeList_iterator_const it_a_end = a.rl.end();
1464 CRangeList_iterator_const it_b_end = b.rl.end();
1465
1466
1467 while (it_a != it_a_end && it_b != it_b_end && *it_a == *it_b )
1468 {
1469 ++it_a;
1470 ++it_b;
1471 }
1472 // return true if a is shorter than b
1473 if (it_a != it_a_end || it_b != it_b_end)
1474 return a.size() < b.size();
1475
1476 return (*it_a < *it_b);
1477 }
1478
1479 friend bool less_than_CRangeList_pointer(const CRangeList *a, const CRangeList *b)
1480 {
1481 return less_than_CRangeList(*a, *b);
1482 }
1483
1484 void transform_start_end(int mult_start, int add_start, int mult_end, int add_end)
1485 {
1486 CRangeList_iterator it = rl.begin();
1487 CRangeList_iterator it_end = rl.end();
1488
1489 while (it != it_end)
1490 {
1491 it->transform_start_end(mult_start, add_start, mult_end, add_end);
1492 ++it;
1493 }
1494 }
1495
1496 void transform_coord(std::vector<unsigned> &coord_trans)
1497 {
1498 CRangeList_iterator it = rl.begin();
1499 CRangeList_iterator it_end = rl.end();
1500
1501 while (it != it_end)
1502 {
1503 it->transform_coord(coord_trans);
1504 ++it;
1505 }
1506 }
1507
1508 }; // End class CRangeList
1509
1510
1511
1512 inline void coverage_values_loop(Crange limit,
1513 CRangeList &rl1,
1514 CRangeList &rl2,
1515 CRangeList &rl3,
1516 CRangeList &rl4,
1517
1518 unsigned &len_gff1,
1519 unsigned &len_gff2,
1520 unsigned &len_gff3,
1521 unsigned &len_gff4,
1522 unsigned &in1not3not4,
1523 unsigned &in2not3not4,
1524 unsigned &in1in2not3not4,
1525 unsigned &in3in4not1not2)
1526 {
1527 unsigned i;
1528 bool in1, in2, in3, in4;
1529
1530 len_gff1=0;
1531 len_gff2=0;
1532 len_gff3=0;
1533 len_gff4=0;
1534 in1not3not4=0;
1535 in2not3not4=0;
1536 in1in2not3not4=0;
1537 in3in4not1not2=0;
1538
1539 unsigned en=limit.end();
1540
1541 CRangeList::CRangeList_iterator_const it1, it2, it3, it4;
1542
1543 it1 = rl1.begin();
1544 it2 = rl2.begin();
1545 it3 = rl3.begin();
1546 it4 = rl4.begin();
1547
1548 rl1.sort();
1549 rl2.sort();
1550 rl3.sort();
1551 rl4.sort();
1552
1553 for (i=limit.begin(); i < en; ++i)
1554 {
1555 // std::cerr << "Checking " << i << std::endl;
1556
1557 in1 = rl1.point_is_in_RangeList(i, it1);
1558 in2 = rl2.point_is_in_RangeList(i, it2);
1559 in3 = rl3.point_is_in_RangeList(i, it3);
1560 in4 = rl4.point_is_in_RangeList(i, it4);
1561
1562 if (in1) ++len_gff1;
1563 if (in2) ++len_gff2;
1564 if (in3) ++len_gff3;
1565 if (in4) ++len_gff4;
1566
1567 if (in1 && !in3 && !in4) ++in1not3not4;
1568 if (in2 && !in3 && !in4) ++in2not3not4;
1569
1570 if ( in1 && in2 && !in3 && !in4) ++in1in2not3not4;
1571 if (!in1 && !in2 && in3 && in4) ++in3in4not1not2;
1572 }
1573 }
1574
1575
1576
1577 // This function is basically used for testing purposes. Its logic is straight forward.
1578
1579 inline void coverage_values_loop(Crange limit,
1580 CRangeList rl1, // no side effect
1581 CRangeList rl2, // no side effect
1582 unsigned &limit_len,
1583 unsigned &len_rl1,
1584 unsigned &len_rl2,
1585 unsigned &len_union,
1586 unsigned &len_intersection)
1587 {
1588 unsigned i;
1589 bool in1, in2;
1590
1591 len_rl1 = 0;
1592 len_rl2 = 0;
1593 len_intersection = 0;
1594 len_union = 0;
1595 limit_len = limit.end() - limit.begin();
1596
1597 unsigned en=limit.end();
1598
1599 CRangeList::CRangeList_iterator_const it1, it2;
1600
1601 it1 = rl1.begin();
1602 it2 = rl2.begin();
1603
1604 rl1.sort();
1605 rl2.sort();
1606
1607 for (i=limit.begin(); i < en; ++i)
1608 {
1609 // std::cerr << "Checking " << i << std::endl;
1610
1611 in1 = rl1.point_is_in_RangeList(i, it1);
1612 in2 = rl2.point_is_in_RangeList(i, it2);
1613
1614 if (in1)
1615 {
1616 ++len_rl1;
1617 ++len_union;
1618 if (in2)
1619 {
1620 --len_union;
1621 ++len_intersection;
1622 }
1623 }
1624 if (in2)
1625 {
1626 ++len_rl2;
1627 ++len_union;
1628 }
1629 }
1630 }
1631
1632 inline void coverage_values(Crange limit,
1633 CRangeList rl1, // no side effect
1634 CRangeList rl2, // no side effect
1635 unsigned &limit_len,
1636 unsigned &len_rl1,
1637 unsigned &len_rl2,
1638 unsigned &len_union,
1639 unsigned &len_intersection)
1640 {
1641 rl1.limit_to_range(limit);
1642 rl2.limit_to_range(limit);
1643
1644 // std::cout << "DEBUG: ";
1645 // rl1.print_bracketed_list(std::cout);
1646 // std::cout << std::endl;
1647
1648 CRangeList un, inter;
1649
1650 un.set_to_range_list_union(rl1,rl2);
1651 inter.set_to_range_list_intersection(rl1,rl2);
1652 limit_len = limit.len();
1653
1654 len_rl1 = rl1.coverage_len();
1655 len_rl2 = rl2.coverage_len();
1656 len_union = un.coverage_len();
1657 len_intersection = inter.coverage_len();
1658 }
1659
1660
1661 inline unsigned overlap(unsigned a1, unsigned a2,
1662 unsigned b1, unsigned b2)
1663 {
1664 unsigned overlap_start = MACRO_MAX(a1, b1);
1665 unsigned overlap_end = MACRO_MIN(a2, b2);
1666
1667 if (overlap_end > overlap_start)
1668 return overlap_end - overlap_start;
1669 else
1670 return 0;
1671 }
1672
1673
1674 inline bool equalRange(unsigned a1, unsigned a2,
1675 unsigned b1, unsigned b2)
1676 {
1677 return (a1 == b1 && a2 == b2);
1678 }
1679
1680
1681 inline bool is_r2_Subrange_of_r1(unsigned a1, unsigned a2, unsigned b1, unsigned b2)
1682 {
1683 return (b1 >= a1 && b2 <= a2);
1684 }
1685
1686
1687 inline void range_intersection(unsigned a1, unsigned a2,
1688 unsigned b1, unsigned b2,
1689 unsigned &c1, unsigned &c2)
1690 {
1691 c1 = MACRO_MAX(a1,b1);
1692 c2 = MACRO_MIN(a2,b2);
1693 if (c1 > c2) // Empty intersection
1694 c1=c2=0;
1695 }
1696
1697 // formerly called range_union. Only if the ranges overlap we have the true union.
1698 inline void range_span(unsigned a1, unsigned a2, // First range
1699 unsigned b1, unsigned b2, // Second range
1700 unsigned &c1, unsigned &c2) // Result range
1701 {
1702 c1 = MACRO_MIN(a1,b1);
1703 c2 = MACRO_MAX(a2,b2);
1704 }
1705
1706
1707
1708 #endif