/* BaitFisher (version 1.2.8) a program for designing DNA target enrichment baits * BaitFilter (version 1.0.6) a program for selecting optimal bait regions * Copyright 2013-2017 by Christoph Mayer * * This source file is part of the BaitFisher-package. * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with BaitFisher. If not, see . * * * For any enquiries send an Email to Christoph Mayer * c.mayer.zfmk@uni-bonn.de * * When publishing work that is based on the results please cite: * Mayer et al. 2016: BaitFisher: A software package for multi-species target DNA enrichment probe design * */ #ifndef RANGE_FUNCTIONS_H #define RANGE_FUNCTIONS_H #include #include #include #include "faststring2.h" #include #include #include #define MACRO_MAX(x,y) ((x)<(y) ? (y) : (x)) #define MACRO_MIN(x,y) ((x)<(y) ? (x) : (y)) // This is a range class for unsigned numbers not for double numbers, which would // be interesting in its own right. // In principle one could make a template class out of this. // // General conventions: // - ranges are undirected // - start <= end // - end is position after last position in range // - ranges can be 0 or 1 based. Be careful!!!! // - the preferred way to represent a vanishing range is (0,0). // TODO: See comments in functions for which this convention does not apply. // TODO: Several functions work independent of a convention here. // class CRangeList; class Crange { friend class CRangeList; unsigned b; unsigned e; public: Crange(unsigned pb, unsigned pe):b(pb), e(pe) { order(); } void order() // According to the conventions above: b <= e { if (b > e) { unsigned tmp = b; b = e; e = tmp; } } friend unsigned overlap(Crange r1, Crange r2) { unsigned overlap_start = MACRO_MAX(r1.b, r2.b); unsigned overlap_end = MACRO_MIN(r1.e, r2.e); if (overlap_end > overlap_start) return overlap_end - overlap_start; else return 0; } friend Crange overlap_range(Crange r1, Crange r2) { unsigned overlap_start = MACRO_MAX(r1.b, r2.b); unsigned overlap_end = MACRO_MIN(r1.e, r2.e); if (overlap_end > overlap_start) { Crange res(overlap_start, overlap_end); return res; } else return Crange(0,0); } friend void overlap_range(Crange r1, Crange r2, Crange &res1, Crange &res_over, Crange &res2) { unsigned overlap_start = MACRO_MAX(r1.b, r2.b); unsigned overlap_end = MACRO_MIN(r1.e, r2.e); unsigned res1_start = MACRO_MIN(r1.b, r2.b); unsigned res2_end = MACRO_MAX(r1.e, r2.e); if (overlap_end > overlap_start) { res_over.assign(overlap_start, overlap_end); res1.assign(res1_start, overlap_start); res2.assign(overlap_end, res2_end); } else { res_over.assign(0, 0); if (r1 < r2) { res1 = r1; res2 = r2; } else { res1 = r2; res2 = r1; } } } friend double overlap_proportion(Crange r1, Crange r2) { unsigned overlap_start = MACRO_MAX(r1.b, r2.b); unsigned overlap_end = MACRO_MIN(r1.e, r2.e); if (overlap_end > overlap_start) { double overl = overlap_end - overlap_start; double l = MACRO_MIN(r1.len(), r2.len()); return (overl/l); } else return 0.0; } friend bool adjacent_or_overlap(Crange r1, Crange r2) { unsigned overlap_start = MACRO_MAX(r1.b, r2.b); unsigned overlap_end = MACRO_MIN(r1.e, r2.e); if (overlap_end >= overlap_start) return true; // == means they are adjacent else return false; } Crange() { b = e = 0; } friend void swap(Crange &r1, Crange &r2) { Crange tmp = r2; r2 = r1; r1 = tmp; } friend void swap(Crange *r1, Crange *r2) { Crange tmp = *r2; *r2 = *r1; *r1 = tmp; } bool empty() const { return (b == e); } void limit_to_range(Crange limit_r) { // Nothing to be done in this case: if (is_r2_Subrange_of_r1(limit_r, *this) ) return; b = MACRO_MAX(limit_r.b, b); e = MACRO_MIN(limit_r.e, e); if (b >= e) b = e = 0; } friend bool operator==(Crange r1, Crange r2) { return (r1.b == r2.b && r1.e == r2.e); } void assign(unsigned pb, unsigned pe) { b = pb; e = pe; order(); } // true if r1 starts before r2 // true if r1 starts with r2 and if r1 is shorter // r1 ******* // r2 *********** r1 < r2 is true friend bool operator<(Crange r1, Crange r2) { if (r1.b != r2.b) return r1.b < r2.b; return r1.e < r2.e; } friend bool equalRange(Crange r1, Crange r2) { return (r1 == r2); } friend bool is_r2_Subrange_of_r1(Crange r1, Crange r2) { return (r2.b >= r1.b && r2.e <= r1.e); } friend Crange range_intersection(Crange r1, Crange r2) { Crange res( MACRO_MAX(r1.b,r2.b), MACRO_MIN(r1.e,r2.e)); if (res.b >= res.e) res.e = res.b = 0; return res; } friend bool before(Crange r1, Crange r2) { return r1.e <= r2.b; } friend bool after(Crange r1, Crange r2) { return r1.b >= r2.e; } // formerly called range_union, which was a misnomer. // friend ...... friend Crange range_span(Crange r1, Crange r2) { Crange res( MACRO_MIN(r1.b,r2.b), MACRO_MAX(r1.e,r2.e)); return res; } void shift (unsigned s) { b +=s; e +=s; } unsigned begin() const { return b; } unsigned end() const { return e; } unsigned inclusive_end() const { return e-1; } unsigned len() const { return e-b; } bool point_is_in_range(unsigned x) const { if (x>=b && x < e) return true; else return false; } bool point_is_behind_range(unsigned x) const { if (x >= e) return true; else return false; } bool point_is_before_range(unsigned x) const { if (x < b) return true; else return false; } void print_with_brackets(std::ostream &os) const { os << "(" << b << "," << e << ")"; } void print_with_brackets_inclusive_end(std::ostream &os) const { os << "(" << b << "," << (e-1) << ")"; } void print_minus_deliminated_inclusive_end(std::ostream &os) const { os << b << "-" << (e-1); } void transform_start_end(int mult_start, int add_start, int mult_end, int add_end) { b = b*mult_start + add_start; e = e*mult_end + add_end; } void transform_coord(std::vector &coord_trans) { // 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. if ( e-1 >= coord_trans.size() ) { std::cerr << "Index out of range: " << e << std::endl; exit(-33); } b = coord_trans[b]; e = coord_trans[e-1]+1; // We transform the coord of the last element and add 1. } }; // class Crange /* class CRangeList_array */ /* { */ /* Crange limit; */ /* faststring rl_array; */ /* CRangeList_array(Crang l):limit(l), faststring('\0', l.end()-l.begin()+1) */ /* {} */ /* Crange get_limit() */ /* { */ /* return limit; */ /* } */ /* unsigned get_limit_begin() */ /* { */ /* return limit.begin(); */ /* } */ /* unsigned get_limit_end() */ /* { */ /* return limit.end(); */ /* } */ /* }; */ // NOTE: Code referring to array is either experimental or unfinished. // // class CRangeList { std::list rl; bool sorted; unsigned lower_bound; unsigned upper_bound; // According to the convention this position comes after the last position in this list of ranges. unsigned count; // Introduced since the empty() function could be // via size()==0, whereas size could be O(n) // which might be very inefficient. // rl_array is not fully implemented: In the future it could be used to store "in" and "out of" the range list // by setting chars to 1 or 0, which would make many functions more efficient. faststring *rl_array; public: typedef std::list::iterator CRangeList_iterator; typedef std::list::const_iterator CRangeList_iterator_const; // Default constructor: // Caution: lower_bound and upper_bound are set to 0, since they are needed by // some functions. This is better than arbitrary values. // even though one could say the values are not correct. // But arbitrary values are not more correct than 0. // Take care that all member functions set these variables // if the first element of a list is added. CRangeList():sorted(false), lower_bound(0), upper_bound(0), count(0), rl_array(NULL) {} // Copy constructor CRangeList(const CRangeList &a):rl(a.rl), lower_bound(a.lower_bound), upper_bound(a.upper_bound), count(a.count), rl_array(NULL) { if (a.rl_array != NULL) { rl_array = new faststring(*a.rl_array); } } void clear_rl_array() { if (rl_array) { delete rl_array; rl_array = NULL; } } ~CRangeList() { clear_rl_array(); } public: void add(unsigned pb, unsigned pe) { Crange new_r (pb, pe); if (new_r.empty()) return; clear_rl_array(); // If the new element is > than the last element in the list, // sorting is not affected, otherwise "it is false". // Note: We cannot set sorted to true, if the rest of the list is not sorted. if (count == 0) { sorted = true; lower_bound = new_r.b; upper_bound = new_r.e; rl.push_back(new_r); } else { if ( !(rl.back() < new_r) ) sorted = false; // else - do not change sorted status if (lower_bound > new_r.b) lower_bound = new_r.b; if (upper_bound < new_r.e) upper_bound = new_r.e; rl.push_back(new_r); } ++count; } CRangeList_iterator_const begin() const { return rl.begin(); } CRangeList_iterator_const begin() { return rl.begin(); } CRangeList_iterator_const end() const { return rl.end(); } CRangeList_iterator_const end() { return rl.end(); } // Test before using this function void create_reset_rl_array() { if (rl_array) { rl_array->assign(upper_bound-lower_bound, '\0'); } else { rl_array = new faststring('\0', upper_bound-lower_bound); } } // Test before using this function void fill_rl_array() { if (rl_array == NULL) create_reset_rl_array(); CRangeList_iterator_const it = rl.begin(); CRangeList_iterator_const it_end = rl.end(); unsigned pos1, pos2; // foreach range: while (it != it_end) { pos1 = it->begin(); pos2 = it->end(); while (pos1 < pos2) { rl_array[pos1] = 1; ++pos1; } ++it; } } void add(Crange new_r) { // If the new element is > than the last element in the list, // sorting is not affected, otherwise "it is false". // Note: We cannot set sorted to true, if the rest of the list is not sorted. clear_rl_array(); if (new_r.empty()) return; if (count == 0) { sorted = true; lower_bound = new_r.b; upper_bound = new_r.e; rl.push_back(new_r); } else { if ( !(rl.back() < new_r) ) sorted = false; // else - do not change sorted status if (lower_bound > new_r.b) lower_bound = new_r.b; if (upper_bound < new_r.e) upper_bound = new_r.e; rl.push_back(new_r); } ++count; } void add(const CRangeList &a) { CRangeList_iterator_const it = a.rl.begin(); CRangeList_iterator_const it_end = a.rl.end(); while (it != it_end) { if ( !it->empty() ) add(*it); ++it; } } bool add(faststring str) { faststring::size_t pos1=0, pos2, len=str.size(); unsigned c1,c2; while (pos1 < len && str[pos1] != ';') { str.skip_symbol(pos1,' '); errno = 0; c1 = str.ToUnsigned(pos1, pos2); // std::cerr << "c1 " << c1 << std::endl; if (errno != 0) { return false; } str.skip_symbol(pos2,' '); if (str[pos2] == ',' || str[pos2] == ';') // One number range. { add(c1,c1+1); } else if (str[pos2] == '-') // Two number range { pos1 = pos2+1; // Be careful '-' is read as minus str.skip_symbol(pos1,' '); // std::cerr << "pos1 " << pos1 << std::endl; errno = 0; c2 = str.ToUnsigned(pos1, pos2); // std::cerr << "c2 " << c2 << std::endl; if (errno != 0) { return false; } // std::cerr << "pos2 " << pos2 << std::endl; str.skip_symbol(pos2,' '); if (str[pos2] > '\0' && str[pos2] <= '\7') { unsigned tmp = c1; unsigned delta = str[pos2]-'\0'; if (errno != 0) { return false; } ++pos2; str.skip_symbol(pos2,' '); while (tmp < c2) { add(tmp, tmp+1); tmp += delta; } } else { add(c1, c2+1); } } else { return false; } pos1 = pos2; if (str[pos1] == ',') // we are not done yet - the list continues { ++pos1; str.skip_symbol(pos1,' '); if (str[pos1] == ';') return false; } } return true; } bool add_delta(faststring str) { faststring::size_t pos1=0, pos2, len=str.size(); unsigned c1,c2; while (pos1 < len && str[pos1] != ';') { str.skip_symbol(pos1,' '); errno = 0; c1 = str.ToUnsigned(pos1, pos2); // std::cerr << "c1 " << c1 << std::endl; if (errno != 0) { return false; } str.skip_symbol(pos2,' '); if (str[pos2] == ',' || str[pos2] == ';') // One number range. { add(c1,c1+1); } else if (str[pos2] == '-') // Two number range { pos1 = pos2+1; // Be careful '-' is read as minus str.skip_symbol(pos1,' '); // std::cerr << "pos1 " << pos1 << std::endl; errno = 0; c2 = str.ToUnsigned(pos1, pos2); // std::cerr << "c2 " << c2 << std::endl; if (errno != 0) { return false; } // std::cerr << "pos2 " << pos2 << std::endl; str.skip_symbol(pos2,' '); if (str[pos2] == '\\') { ++pos2; str.skip_symbol(pos2,' '); char d = str[pos2]; unsigned tmp = c1; unsigned delta = d-'0'; if (errno != 0) { return false; } ++pos2; str.skip_symbol(pos2,' '); while (tmp < c2) { add(tmp, tmp+1); tmp += delta; } } else { add(c1, c2+1); } } else { return false; } pos1 = pos2; if (str[pos1] == ',') // we are not done yet - the list continues { ++pos1; str.skip_symbol(pos1,' '); if (str[pos1] == ';') return false; } } return true; } unsigned size() const { return count; } // Assignment operator: Use standard assignment operator. No pointer content needs to be copied // This is still true since rl_array is not ready to use yet. // Currently there is no need/no plan to implement it. void clear() { rl.clear(); // Will call the destructor for all objects. sorted = false; clear_rl_array(); // I am not sure this is the best way to assign values to the bounds. // Bounds are not well defined for an empty list. lower_bound = upper_bound = 0; count = 0; } void sort() { if (!sorted) { rl.sort(); sorted = true; } } // We expect the use to check for count == 0 Crange bounds() { // There is one problem here: The last entry need to have the "highest coordinate" // 100-150, 200-400, 250-300 Crange res(lower_bound, upper_bound); return res; } // We expect the use to check for count == 0 unsigned get_lower_bound() { return lower_bound; } // We expect the use to check for count == 0 unsigned get_upper_bound() { return upper_bound; } // Find an island of overlapping ranges, starting at it_beg. // The initial value of it_end (the second parameter) is overwritten, // and is therefore irrelevant. // When leaving this function, it_end points to the range behind the island. // This is also true, if the island is the last island in the list. // In this case, it_end == to list_of_sat_ptr.end() unsigned findOverlappingIsland(CRangeList_iterator_const it_beg, CRangeList_iterator_const &it_end) const { unsigned count=1; it_end = it_beg; ++it_end; while (it_end != rl.end()) { if (overlap(*it_beg, *it_end)) // If they overlap, we move it_end, { ++count; ++it_end; } else // if they do not overlap any more, we need not be out of the island. { // Let us move it_beg, which should now be behind or equal to it_end. ++it_beg; if (it_beg == it_end) // this is the case of the last two sats do not overlap break; // In this case it_end points one behind the last island. } } return count; } unsigned findAdjacentIsland(CRangeList_iterator_const it_beg, CRangeList_iterator_const &it_end) const { unsigned count=1; // The current range is the Nr 1. it_end = it_beg; ++it_end; while (it_end != rl.end()) { if (adjacent_or_overlap(*it_beg, *it_end)) // If they overlap, we move it_end, { ++count; ++it_end; } else // if they do not overlap any more, we need not be out of the island. { // Let us move it_beg, which should now be behind or equal to it_end. ++it_beg; if (it_beg == it_end) // this is the case of the last two sats do not overlap break; // In this case it_end points one behind the last island. } } return count; } void findRangeWithMaxExtToRight(CRangeList_iterator_const it_beg, CRangeList_iterator_const it_end, CRangeList_iterator_const &it_extends_most) const { it_extends_most = it_beg; if (it_beg == it_end) return; ++it_beg; while (it_beg != it_end) { if ((*it_beg).e > (*it_extends_most).e ) it_extends_most = it_beg; ++it_beg; } } Crange range_of_island(CRangeList_iterator_const it_beg, CRangeList_iterator_const &it_end_of_island) { Crange res; CRangeList_iterator_const it_extends_most; if (!sorted) { std::cerr << "Error: range_of_island requires the list of ranges to be sorted." << std::endl; exit(0); } res.b = it_beg->b; findOverlappingIsland(it_beg, it_end_of_island); findRangeWithMaxExtToRight(it_beg, it_end_of_island, it_extends_most); res.e = it_extends_most->e; return res; } Crange range_of_adjacentisland(CRangeList_iterator_const it_beg, CRangeList_iterator_const &it_end_of_island) { Crange res; CRangeList_iterator_const it_extends_most; if (!sorted) { std::cerr << "Internal error: range_of_adjacentisland requires the list of ranges to be sorted." << std::endl; exit(0); } res.b = it_beg->b; findAdjacentIsland(it_beg, it_end_of_island); findRangeWithMaxExtToRight(it_beg, it_end_of_island, it_extends_most); res.e = it_extends_most->e; return res; } // coverage_len allows us to specify a range - double check that feature. double coverage_rel(Crange bds) { CRangeList rl_tmp(*this); rl_tmp.limit_to_range(bds); double bds_len = bds.len(); return rl_tmp.coverage_len(bds)/bds_len; } unsigned coverage_len2(Crange bds) { CRangeList rl2; get_consolidated_range_list(rl2); rl2.limit_to_range(bds); return rl2.coverage_raw(); } unsigned coverage_raw() { unsigned lencount=0; CRangeList_iterator_const it, it_end; it = rl.begin(); it_end = rl.end(); while (it != it_end) { lencount += it->len(); ++it; } return lencount; } // Side effect: *this will be sorted unsigned coverage_len(Crange bds) // bounds in which to compute the coverage { unsigned cover = 0; CRangeList_iterator_const it, it_end, end_island; Crange r1, r2; // std::cerr << "Computing coverage for this: " << std::endl; // print_bracketed_list(std::cerr); // std::cerr << std::endl; sort(); it = rl.begin(); it_end = rl.end(); while (it != it_end && it->e < bds.b) ++it; if (it == it_end) return 0; // it points to first range after start of bds r1 = range_of_island(it, end_island); cover += overlap(r1, bds); it = end_island; // std::cerr << "First overlap: " << cover << std::endl; while (it != it_end && it->b < bds.e) { r1 = range_of_island(it, end_island); it = end_island; if (r1.e > bds.e) { cover += overlap(r1, bds); break; } else cover += r1.len(); // std::cerr << "next value: " << cover << std::endl; } return cover; } // Side effect: *this will be sorted unsigned coverage_len() // without bounds { unsigned cover = 0; CRangeList_iterator_const it, it_end, end_island; Crange r1; // std::cerr << "Computing coverage for this: " << std::endl; // print_bracketed_list(std::cerr); // std::cerr << std::endl; sort(); it = rl.begin(); it_end = rl.end(); while (it != it_end) { r1 = range_of_island(it, end_island); it = end_island; cover += r1.len(); // std::cerr << "next value: " << cover << std::endl; } return cover; } unsigned coverage_len_loop() // without bounds { unsigned cover = 0; Crange r1, b; // std::cerr << "Computing coverage for this: " << std::endl; // print_bracketed_list(std::cerr); // std::cerr << std::endl; if (count == 0) return 0; // Required by point_is_in_RangeList sort(); CRangeList_iterator_const it1 = rl.begin(); b = bounds(); //Upper bound of this range is element after range. unsigned i, b_end; b_end = b.end(); for (i=b.begin(); iprint_with_brackets(os); ++it_beg; if (it_beg == it_end) return; os << ","; } } void print_bracketed_list_inclusive_ends(std::ostream &os) const { CRangeList_iterator_const it_beg = rl.begin(); CRangeList_iterator_const it_end = rl.end(); if (it_beg == it_end) return; while (1) //(it_beg != it_end) { it_beg->print_with_brackets_inclusive_end(os); ++it_beg; if (it_beg == it_end) return; os << ","; } } void print_deliminated_inclusive_end(std::ostream &os, const char *delim) const { CRangeList_iterator_const it_beg = rl.begin(); CRangeList_iterator_const it_end = rl.end(); if (it_beg == it_end) return; while (1) //(it_beg != it_end) { it_beg->print_minus_deliminated_inclusive_end(os); ++it_beg; if (it_beg == it_end) return; os << delim; } } void print_deliminated_inclusive_end(std::ostream &os, char delim= ',') const { CRangeList_iterator_const it_beg = rl.begin(); CRangeList_iterator_const it_end = rl.end(); if (it_beg == it_end) return; while (1) //(it_beg != it_end) { it_beg->print_minus_deliminated_inclusive_end(os); ++it_beg; if (it_beg == it_end) return; os << delim; } } // For this CRangeList compute a consolidated range list: // Adjacent or overlapping ranges are merged in the consolidated list void get_consolidated_range_list(CRangeList &crl) { sort(); crl.clear(); CRangeList_iterator_const it1, it2; it1 = it2 = rl.begin(); while (it2 != rl.end() ) { crl.add(range_of_adjacentisland(it1, it2) ); // crl.sort(); it1 = it2; } } void remove_empty() // Now we try to avoid to add empty ranges in the first place { CRangeList_iterator it1; it1 = rl.begin(); while (it1 != rl.end() ) { if ( it1->empty() ) { it1 = rl.erase(it1); --count; } else ++it1; } } // Side effect: Removes empty ranges form list: void limit_to_range(Crange limit_r) { CRangeList_iterator it1; clear_rl_array(); it1 = rl.begin(); if (sorted) { // std::cout << "sorted mode" << std::endl; while (it1 != rl.end() && before(*it1, limit_r) ) { // remove ranges before limiting range: ++it1; } if (it1 != rl.begin()) rl.erase(rl.begin(), it1); // count will be reset at the end!! while (it1 != rl.end() && !after(*it1, limit_r) ) { it1->limit_to_range(limit_r); if ( it1->empty() ) { it1 = rl.erase(it1); // count will be reset at the end!! } else ++it1; } if (it1 != rl.end() ) { // remove ranges after limiting range: rl.erase(it1, rl.end()); // count will be reset at the end!! } } else { while (it1 != rl.end() ) { it1->limit_to_range(limit_r); if ( it1->empty() ) { it1 = rl.erase(it1); // count will be reset at the end!! } else ++it1; } } // This could be made a bit more efficient. // This solution however is most secure. count = rl.size(); } friend CRangeList range_union(Crange a, Crange b) { CRangeList tmp, res; tmp.add(a); tmp.add(b); tmp.get_consolidated_range_list(res); return res; } friend CRangeList cut_out_range(Crange a, Crange b) { Crange r1, r2, r3; CRangeList res; overlap_range(a,b,r1, r2, r3); res.add(r1); res.add(r3); return res; } void set_to_range_list_union(const CRangeList &a, const CRangeList &b) { CRangeList tmp(a); tmp.add(b); clear(); tmp.get_consolidated_range_list(*this); } void set_to_range_list_intersection(CRangeList &a, CRangeList &b) { clear(); CRangeList ca, cb; a.get_consolidated_range_list(ca); b.get_consolidated_range_list(cb); CRangeList_iterator_const it_a, it_b; it_a = ca.rl.begin(); it_b = cb.rl.begin(); while (it_a != ca.rl.end() ) { // While the range it_b lies before it_a: while ( it_b != cb.rl.end() && before(*it_b, *it_a) ) { ++it_b; } // While the range it_a overlaps with it_b: while ( it_b != cb.rl.end() && overlap(*it_a, *it_b) ) { add(range_intersection(*it_a, *it_b) ); ++it_b; } if (it_b != cb.rl.begin()) --it_b; ++it_a; } } // Side effect: list of ranges will be sorted bool point_is_in_RangeList(unsigned x) { sort(); CRangeList_iterator_const it1, it2; it1 = rl.begin(); it2 = rl.end(); // Skip all ranges which have an end value that lies before x while (it1 != it2 && x >= it1->e) { ++it1; } // Test all ranges which have a beginning that lies before x while (it1 != it2 && x >= it1->b) { if (it1->point_is_in_range(x)) return true; ++it1; } // All remaining ranges have a beginning that lies behind x: return false; } // Requirement: list of ranges must be sorted bool point_is_in_RangeList(unsigned x, CRangeList_iterator_const &it1) const { if (!sorted) { std::cerr << "When calling point_is_in_RangeList, the range list must be sorted." << std::endl; exit(-11); } CRangeList_iterator_const it2; it2 = rl.end(); // Skip all ranges which have an end value that lies before x while (it1 != it2 && x >= it1->e) { ++it1; } // Test all ranges which have a beginning that lies before x while (it1 != it2 && x >= it1->b) { if (it1->point_is_in_range(x)) return true; ++it1; } if (it1 != rl.begin() ) --it1; // We might have moved too far. // All remaining ranges have a beginning that lies behind x: return false; } void export_as_gff(std::ostream &os, const char *seq, const char* source, const char *type, char direction) { CRangeList_iterator_const it = rl.begin(); CRangeList_iterator_const it_end = rl.end(); while (it != it_end) { os << seq << "\t" << source << "\t" << type << "\t" << it->b << "\t" << it->e << "\t" << ".\t" << direction << "\t" << ".\t" << "ID=" << seq << "_" << it->b << "_" << it->e << std::endl; ++it; } } // Side effect: CRangeList rl is being sorted and set to a consolidated list. void set_to_complement_of(CRangeList &rl, Crange limit) { CRangeList crl; Crange r1, r2, r3; // Clear this CRangeList. Otherwise we add to a probably non empty list. clear(); rl.get_consolidated_range_list(crl); crl.sort(); // Should already be sorted. Just to be sure. crl.limit_to_range(limit); CRangeList_iterator_const it = crl.rl.begin(); CRangeList_iterator_const it_end = crl.rl.end(); r3 = limit; while (it != it_end) { // r2 is just a dummy for the overlapping part. overlap_range(r3, *it, r1, r2, r3); // std::cerr << "Adding "; r1.print_with_brackets(std::cerr); std::cerr << std::endl; add(r1); ++it; } add(r3); } unsigned* get_range_list_field() { unsigned* p = new unsigned [2*count]; CRangeList_iterator_const it = rl.begin(); CRangeList_iterator_const it_end = rl.end(); unsigned i=0; sort(); while (it != it_end) { p[i] = it->begin(); p[i+1] = it->end(); ++i; ++it; } return p; } friend bool less_than_CRangeList(const CRangeList &a, const CRangeList &b) { CRangeList_iterator_const it_a = a.rl.begin(); CRangeList_iterator_const it_b = b.rl.begin(); CRangeList_iterator_const it_a_end = a.rl.end(); CRangeList_iterator_const it_b_end = b.rl.end(); while (it_a != it_a_end && it_b != it_b_end && *it_a == *it_b ) { ++it_a; ++it_b; } // return true if a is shorter than b if (it_a != it_a_end || it_b != it_b_end) return a.size() < b.size(); return (*it_a < *it_b); } friend bool less_than_CRangeList_pointer(const CRangeList *a, const CRangeList *b) { return less_than_CRangeList(*a, *b); } void transform_start_end(int mult_start, int add_start, int mult_end, int add_end) { CRangeList_iterator it = rl.begin(); CRangeList_iterator it_end = rl.end(); while (it != it_end) { it->transform_start_end(mult_start, add_start, mult_end, add_end); ++it; } } void transform_coord(std::vector &coord_trans) { CRangeList_iterator it = rl.begin(); CRangeList_iterator it_end = rl.end(); while (it != it_end) { it->transform_coord(coord_trans); ++it; } } }; // End class CRangeList inline void coverage_values_loop(Crange limit, CRangeList &rl1, CRangeList &rl2, CRangeList &rl3, CRangeList &rl4, unsigned &len_gff1, unsigned &len_gff2, unsigned &len_gff3, unsigned &len_gff4, unsigned &in1not3not4, unsigned &in2not3not4, unsigned &in1in2not3not4, unsigned &in3in4not1not2) { unsigned i; bool in1, in2, in3, in4; len_gff1=0; len_gff2=0; len_gff3=0; len_gff4=0; in1not3not4=0; in2not3not4=0; in1in2not3not4=0; in3in4not1not2=0; unsigned en=limit.end(); CRangeList::CRangeList_iterator_const it1, it2, it3, it4; it1 = rl1.begin(); it2 = rl2.begin(); it3 = rl3.begin(); it4 = rl4.begin(); rl1.sort(); rl2.sort(); rl3.sort(); rl4.sort(); for (i=limit.begin(); i < en; ++i) { // std::cerr << "Checking " << i << std::endl; in1 = rl1.point_is_in_RangeList(i, it1); in2 = rl2.point_is_in_RangeList(i, it2); in3 = rl3.point_is_in_RangeList(i, it3); in4 = rl4.point_is_in_RangeList(i, it4); if (in1) ++len_gff1; if (in2) ++len_gff2; if (in3) ++len_gff3; if (in4) ++len_gff4; if (in1 && !in3 && !in4) ++in1not3not4; if (in2 && !in3 && !in4) ++in2not3not4; if ( in1 && in2 && !in3 && !in4) ++in1in2not3not4; if (!in1 && !in2 && in3 && in4) ++in3in4not1not2; } } // This function is basically used for testing purposes. Its logic is straight forward. inline void coverage_values_loop(Crange limit, CRangeList rl1, // no side effect CRangeList rl2, // no side effect unsigned &limit_len, unsigned &len_rl1, unsigned &len_rl2, unsigned &len_union, unsigned &len_intersection) { unsigned i; bool in1, in2; len_rl1 = 0; len_rl2 = 0; len_intersection = 0; len_union = 0; limit_len = limit.end() - limit.begin(); unsigned en=limit.end(); CRangeList::CRangeList_iterator_const it1, it2; it1 = rl1.begin(); it2 = rl2.begin(); rl1.sort(); rl2.sort(); for (i=limit.begin(); i < en; ++i) { // std::cerr << "Checking " << i << std::endl; in1 = rl1.point_is_in_RangeList(i, it1); in2 = rl2.point_is_in_RangeList(i, it2); if (in1) { ++len_rl1; ++len_union; if (in2) { --len_union; ++len_intersection; } } if (in2) { ++len_rl2; ++len_union; } } } inline void coverage_values(Crange limit, CRangeList rl1, // no side effect CRangeList rl2, // no side effect unsigned &limit_len, unsigned &len_rl1, unsigned &len_rl2, unsigned &len_union, unsigned &len_intersection) { rl1.limit_to_range(limit); rl2.limit_to_range(limit); // std::cout << "DEBUG: "; // rl1.print_bracketed_list(std::cout); // std::cout << std::endl; CRangeList un, inter; un.set_to_range_list_union(rl1,rl2); inter.set_to_range_list_intersection(rl1,rl2); limit_len = limit.len(); len_rl1 = rl1.coverage_len(); len_rl2 = rl2.coverage_len(); len_union = un.coverage_len(); len_intersection = inter.coverage_len(); } inline unsigned overlap(unsigned a1, unsigned a2, unsigned b1, unsigned b2) { unsigned overlap_start = MACRO_MAX(a1, b1); unsigned overlap_end = MACRO_MIN(a2, b2); if (overlap_end > overlap_start) return overlap_end - overlap_start; else return 0; } inline bool equalRange(unsigned a1, unsigned a2, unsigned b1, unsigned b2) { return (a1 == b1 && a2 == b2); } inline bool is_r2_Subrange_of_r1(unsigned a1, unsigned a2, unsigned b1, unsigned b2) { return (b1 >= a1 && b2 <= a2); } inline void range_intersection(unsigned a1, unsigned a2, unsigned b1, unsigned b2, unsigned &c1, unsigned &c2) { c1 = MACRO_MAX(a1,b1); c2 = MACRO_MIN(a2,b2); if (c1 > c2) // Empty intersection c1=c2=0; } // formerly called range_union. Only if the ranges overlap we have the true union. inline void range_span(unsigned a1, unsigned a2, // First range unsigned b1, unsigned b2, // Second range unsigned &c1, unsigned &c2) // Result range { c1 = MACRO_MIN(a1,b1); c2 = MACRO_MAX(a2,b2); } #endif