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 601341 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
38 #include <util/align_range_coll.hpp>
39 #include <objtools/alnmgr/aln_rng_coll_oper.hpp>
40
41
42 BEGIN_NCBI_SCOPE
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>
SubtractAlnRngCollections(const CAlignRangeCollectionList<TAlnRng> & minuend,const CAlignRangeCollectionList<TAlnRng> & subtrahend,CAlignRangeCollectionList<TAlnRng> & difference)49 void SubtractAlnRngCollections(
50 const CAlignRangeCollectionList<TAlnRng>& minuend,
51 const CAlignRangeCollectionList<TAlnRng>& subtrahend,
52 CAlignRangeCollectionList<TAlnRng>& difference)
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>
SubtractOnFirst(const TAlnRng & minuend,const CAlignRangeCollectionList<TAlnRng> & subtrahend,CAlignRangeCollectionList<TAlnRng> & difference)75 void SubtractOnFirst(
76 const TAlnRng& minuend,
77 const CAlignRangeCollectionList<TAlnRng>& subtrahend,
78 CAlignRangeCollectionList<TAlnRng>& difference)
79 {
80 typename CAlignRangeCollectionList<TAlnRng>::TIndexByFirst::const_iterator r_it;
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>
SubtractOnSecond(const TAlnRng & minuend,const CAlignRangeCollectionList<TAlnRng> & subtrahend,CAlignRangeCollectionList<TAlnRng> & difference)138 void SubtractOnSecond(
139 const TAlnRng& minuend,
140 const CAlignRangeCollectionList<TAlnRng>& subtrahend,
141 CAlignRangeCollectionList<TAlnRng>& difference)
142 {
143 if (minuend.GetSecondFrom() < 0) {
144 difference.insert(minuend);
145 return;
146 }
147
148 typename CAlignRangeCollectionList<TAlnRng>::TIndexBySecond::const_iterator r_it;
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
206 END_NCBI_SCOPE
207
208 #endif // OBJTOOLS_ALNMGR__ALN_RNG_COLL_LIST_OPER__HPP
209