NCBI C++ ToolKit
aln_rng_coll_list_oper.hpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1 #ifndef OBJTOOLS_ALNMGR__ALN_RNG_COLL_LIST_OPER__HPP
2 #define OBJTOOLS_ALNMGR__ALN_RNG_COLL_LIST_OPER__HPP
3 /* $Id: aln_rng_coll_list_oper.hpp 88953 2020-02-05 20:27:33Z vasilche $
4 * ===========================================================================
5 *
6 * PUBLIC DOMAIN NOTICE
7 * National Center for Biotechnology Information
8 *
9 * This software/database is a "United States Government Work" under the
10 * terms of the United States Copyright Act. It was written as part of
11 * the author's official duties as a United States Government employee and
12 * thus cannot be copyrighted. This software/database is freely available
13 * to the public for use. The National Library of Medicine and the U.S.
14 * Government have not placed any restriction on its use or reproduction.
15 *
16 * Although all reasonable efforts have been taken to ensure the accuracy
17 * and reliability of the software and data, the NLM and the U.S.
18 * Government do not and cannot warrant the performance or results that
19 * may be obtained by using this software or data. The NLM and the U.S.
20 * Government disclaim all warranties, express or implied, including
21 * warranties of performance, merchantability or fitness for any particular
22 * purpose.
23 *
24 * Please cite the author in any work or product based on this material.
25 *
26 * ===========================================================================
27 *
28 * Author: Kamen Todorov, NCBI
29 *
30 * File Description:
31 * CAlignRangeCollection operations
32 *
33 */
34 
35 
36 #include <corelib/ncbistd.hpp>
37 
40 
41 
43 
44 
45 /// Subtract one range collection from another. Both first and second
46 /// sequences are checked, so that the result does not intersect with
47 /// any row of the minuend.
48 template<class TAlnRng>
51  const CAlignRangeCollectionList<TAlnRng>& subtrahend,
53 {
54  typedef CAlignRangeCollectionList<TAlnRng> TAlnRngColl;
55  _ASSERT( !subtrahend.empty() );
56 
57  // Calc differece on the first row
58  TAlnRngColl difference_on_first(minuend.GetPolicyFlags());
59  for ( auto& minuend_it : minuend.GetIndexByFirst()) {
60  SubtractOnFirst(*minuend_it,
61  subtrahend,
62  difference_on_first);
63  }
64 
65  // Second row
66  for ( auto& minuend_it : difference_on_first.GetIndexBySecond()) {
67  SubtractOnSecond(*minuend_it,
68  subtrahend,
69  difference);
70  }
71 }
72 
73 
74 template<class TAlnRng>
76  const TAlnRng& minuend,
77  const CAlignRangeCollectionList<TAlnRng>& subtrahend,
79 {
81  r_it = subtrahend.GetIndexByFirst().upper_bound(minuend.GetFirstFrom());
82  if ( r_it != subtrahend.GetIndexByFirst().begin() ) {
83  --r_it;
84  if ( (*r_it)->GetFirstToOpen() <= minuend.GetFirstFrom() ) {
85  ++r_it;
86  }
87  }
88 
89  if (r_it == subtrahend.GetIndexByFirst().end()) {
90  difference.insert(minuend);
91  return;
92  }
93 
94  int trim; // whether and how much to trim when truncating
95 
96  trim = (*r_it)->GetFirstFrom() <= minuend.GetFirstFrom();
97 
98  TAlnRng r = minuend;
99  TAlnRng tmp_r;
100 
101  while (1) {
102  if (trim) {
103  // x--------)
104  // ...---...
105  trim = (*r_it)->GetFirstToOpen() - r.GetFirstFrom();
106  TrimFirstFrom(r, trim);
107  if ((int) r.GetLength() <= 0) {
108  return;
109  }
110  ++r_it;
111  if (r_it == subtrahend.GetIndexByFirst().end()) {
112  difference.insert(r);
113  return;
114  }
115  }
116 
117  // x------)
118  // x--...
119  trim = r.GetFirstToOpen() - (*r_it)->GetFirstFrom();
120 
121  if (trim <= 0) {
122  // x----)
123  // x--)
124  difference.insert(r);
125  return;
126  }
127  else {
128  // x----)
129  // x----...
130  tmp_r = r;
131  TrimFirstTo(tmp_r, trim);
132  difference.insert(tmp_r);
133  }
134  }
135 }
136 
137 template<class TAlnRng>
139  const TAlnRng& minuend,
140  const CAlignRangeCollectionList<TAlnRng>& subtrahend,
142 {
143  if (minuend.GetSecondFrom() < 0) {
144  difference.insert(minuend);
145  return;
146  }
147 
149  r_it = subtrahend.GetIndexBySecond().upper_bound(minuend.GetSecondFrom());
150  if ( r_it != subtrahend.GetIndexBySecond().begin() ) {
151  --r_it;
152  if ( (*r_it)->GetSecondToOpen() <= minuend.GetSecondFrom() ) {
153  ++r_it;
154  }
155  }
156 
157  if (r_it == subtrahend.GetIndexBySecond().end()) {
158  difference.insert(minuend);
159  return;
160  }
161 
162  int trim; // whether and how much to trim when truncating
163 
164  trim = (*r_it)->GetSecondFrom() <= minuend.GetSecondFrom();
165 
166  TAlnRng r = minuend;
167  TAlnRng tmp_r;
168 
169  while (1) {
170  if (trim) {
171  // x--------)
172  // ...---...
173  trim = (*r_it)->GetSecondToOpen() - r.GetSecondFrom();
174  TrimSecondFrom(r, trim);
175  if ((int) r.GetLength() <= 0) {
176  return;
177  }
178  ++r_it;
179  if (r_it == subtrahend.GetIndexBySecond().end()) {
180  difference.insert(r);
181  return;
182  }
183  }
184 
185  // x------)
186  // x--...
187  trim = r.GetSecondToOpen() - (*r_it)->GetSecondFrom();
188 
189  if (trim <= 0) {
190  // x----)
191  // x--)
192  difference.insert(r);
193  return;
194  }
195  else {
196  // x----)
197  // x----...
198  tmp_r = r;
199  TrimSecondTo(tmp_r, trim);
200  difference.insert(tmp_r);
201  }
202  }
203 }
204 
205 
207 
208 #endif // OBJTOOLS_ALNMGR__ALN_RNG_COLL_LIST_OPER__HPP
void SubtractOnSecond(const TAlnRng &minuend, const CAlignRangeCollectionList< TAlnRng > &subtrahend, CAlignRangeCollectionList< TAlnRng > &difference)
void SubtractAlnRngCollections(const CAlignRangeCollectionList< TAlnRng > &minuend, const CAlignRangeCollectionList< TAlnRng > &subtrahend, CAlignRangeCollectionList< TAlnRng > &difference)
Subtract one range collection from another.
void SubtractOnFirst(const TAlnRng &minuend, const CAlignRangeCollectionList< TAlnRng > &subtrahend, CAlignRangeCollectionList< TAlnRng > &difference)
void TrimSecondTo(TAlnRng &rng, int trim)
void TrimFirstFrom(TAlnRng &rng, int trim)
void TrimFirstTo(TAlnRng &rng, int trim)
void TrimSecondFrom(TAlnRng &rng, int trim)
class CAlignRangeCollectionList<TAlignRange> represent a sorted collection of TAlignRange.
const_iterator insert(const TAlignRange &r)
const TIndexByFirst & GetIndexByFirst() const
const TIndexBySecond & GetIndexBySecond() const
const_iterator begin() const
Definition: set.hpp:286
const_iterator upper_bound(const key_type &key) const
Definition: set.hpp:290
const_iterator end() const
Definition: set.hpp:287
parent_type::const_iterator const_iterator
Definition: set.hpp:197
Include a standard set of the NCBI C++ Toolkit most basic headers.
#define END_NCBI_SCOPE
End previously defined NCBI scope.
Definition: ncbistl.hpp:103
#define BEGIN_NCBI_SCOPE
Define ncbi namespace.
Definition: ncbistl.hpp:100
double r(size_t dimension_, const Int4 *score_, const double *prob_, double theta_)
#define _ASSERT
Modified on Fri Mar 01 10:05:03 2024 by modify_doxy.py rev. 669887