1 /* $Id: alndiag.cpp 115669 2007-12-17 19:36:28Z ucko $
2 * ===========================================================================
3 *
4 * PUBLIC DOMAIN NOTICE
5 * National Center for Biotechnology Information
6 *
7 * This software/database is a "United States Government Work" under the
8 * terms of the United States Copyright Act. It was written as part of
9 * the author's official duties as a United States Government employee and
10 * thus cannot be copyrighted. This software/database is freely available
11 * to the public for use. The National Library of Medicine and the U.S.
12 * Government have not placed any restriction on its use or reproduction.
13 *
14 * Although all reasonable efforts have been taken to ensure the accuracy
15 * and reliability of the software and data, the NLM and the U.S.
16 * Government do not and cannot warrant the performance or results that
17 * may be obtained by using this software or data. The NLM and the U.S.
18 * Government disclaim all warranties, express or implied, including
19 * warranties of performance, merchantability or fitness for any particular
20 * purpose.
21 *
22 * Please cite the author in any work or product based on this material.
23 *
24 * ===========================================================================
25 *
26 * Author: Kamen Todorov, NCBI
27 *
28 * File Description:
29 * Collection of diagonal alignment ranges.
30 *
31 * ===========================================================================
32 */
33
34
35 #include <ncbi_pch.hpp>
36
37 #include <objtools/alnmgr/alndiag.hpp>
38 #include <algorithm>
39
40
41 BEGIN_NCBI_SCOPE
42
43
CDiagRangeCollection(int first_width,int second_width)44 CDiagRangeCollection::CDiagRangeCollection(int first_width, int second_width)
45 : TAlnRngColl(TAlnRngColl::fKeepNormalized | TAlnRngColl::fAllowMixedDir),
46 m_Extender(*this),
47 m_FirstWidth(first_width),
48 m_SecondWidth(second_width)
49 {
50 };
51
52
Diff(const TAlnRngColl & substrahend,TAlnRngColl & difference)53 void CDiagRangeCollection::Diff(const TAlnRngColl& substrahend,
54 TAlnRngColl& difference)
55 {
56 if (empty()) {
57 ITERATE (TAlnRngColl, substrahend_it, substrahend) {
58 difference.insert(*substrahend_it);
59 }
60 return;
61 }
62
63 TAlnRngColl difference_on_first;
64 {
65 TAlnRngColl::const_iterator minuend_it = begin();
66 ITERATE (TAlnRngColl, substrahend_it, substrahend) {
67 x_Diff(*substrahend_it,
68 difference_on_first,
69 minuend_it);
70 }
71 }
72
73 {
74 m_Extender.Init(*this); /// HACK!
75 m_Extender.UpdateIndex();
76 TAlnRngCollExt::const_iterator minuend_it = m_Extender.begin();
77 TAlnRngCollExt diff_on_first_ext(difference_on_first);
78 diff_on_first_ext.UpdateIndex();
79 ITERATE (TAlnRngCollExt,
80 substrahend_it,
81 diff_on_first_ext) {
82 x_DiffSecond(*(substrahend_it->second),
83 difference,
84 minuend_it);
85 }
86 }
87 }
88
89
x_Diff(const TAlnRng & rng,TAlnRngColl & result,TAlnRngColl::const_iterator & r_it)90 void CDiagRangeCollection::x_Diff(const TAlnRng& rng,
91 TAlnRngColl& result,
92 TAlnRngColl::const_iterator& r_it)
93 {
94 PAlignRangeToLess<TAlnRng> p;
95
96 r_it = std::lower_bound(r_it, end(), rng.GetFirstFrom(), p); /* NCBI_FAKE_WARNING: WorkShop */
97
98 if (r_it == end()) {
99 result.insert(rng);
100 return;
101 }
102
103 int trim; // whether and how much to trim when truncating
104
105 trim = (r_it->GetFirstFrom() <= rng.GetFirstFrom());
106
107 TAlnRng r = rng;
108 TAlnRng tmp_r;
109
110 while (1) {
111 if (trim) {
112 // x--------)
113 // ...---...
114 trim = r_it->GetFirstToOpen() - r.GetFirstFrom();
115 TrimFirstFrom(r, trim / m_FirstWidth);
116 if ((int) r.GetLength() <= 0) {
117 return;
118 }
119 ++r_it;
120 if (r_it == end()) {
121 result.insert(r);
122 return;
123 }
124 }
125
126 // x------)
127 // x--...
128 trim = r.GetFirstToOpen() - r_it->GetFirstFrom();
129
130 if (trim <= 0) {
131 // x----)
132 // x--)
133 result.insert(r);
134 return;
135 } else {
136 // x----)
137 // x----...
138 tmp_r = r;
139 TrimFirstTo(tmp_r, trim / m_FirstWidth);
140 result.insert(tmp_r);
141 }
142 }
143 }
144
145
x_DiffSecond(const TAlnRng & rng,TAlnRngColl & result,TAlnRngCollExt::const_iterator & r_it)146 void CDiagRangeCollection::x_DiffSecond(const TAlnRng& rng,
147 TAlnRngColl& result,
148 TAlnRngCollExt::const_iterator& r_it)
149 {
150 PItLess p;
151
152 m_Extender.UpdateIndex();
153 r_it = std::lower_bound(r_it, m_Extender.end(), rng.GetSecondFrom(), p); /* NCBI_FAKE_WARNING: WorkShop */
154 if (r_it == m_Extender.end()) {
155 result.insert(rng);
156 return;
157 }
158
159 int trim; // whether and how much to trim when truncating
160
161 trim = (r_it->second->GetSecondFrom() <= rng.GetSecondFrom());
162
163 TAlnRng r = rng;
164 TAlnRng tmp_r;
165
166 while (1) {
167 if (trim) {
168 // x--------)
169 // ...---...
170 trim = r_it->second->GetSecondToOpen() - r.GetSecondFrom();
171 TrimSecondFrom(r, trim / m_SecondWidth);
172 if ((int) r.GetLength() <= 0) {
173 return;
174 }
175 ++r_it;
176 if (r_it == m_Extender.end()) {
177 result.insert(r);
178 return;
179 }
180 }
181
182 // x------)
183 // x--...
184 trim = r.GetSecondToOpen() - r_it->second->GetSecondFrom();
185
186 if (trim <= 0) {
187 // x----)
188 // x--)
189 result.insert(r);
190 return;
191 } else {
192 // x----)
193 // x----...
194 tmp_r = r;
195 TrimSecondTo(tmp_r, trim / m_SecondWidth);
196 result.insert(tmp_r);
197 }
198 }
199 }
200
201
202 END_NCBI_SCOPE
203