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