1 // ==========================================================================
2 // SeqAn - The Library for Sequence Analysis
3 // ==========================================================================
4 // Copyright (c) 2006-2015, Knut Reinert, FU Berlin
5 // All rights reserved.
6 //
7 // Redistribution and use in source and binary forms, with or without
8 // modification, are permitted provided that the following conditions are met:
9 //
10 // * Redistributions of source code must retain the above copyright
11 // notice, this list of conditions and the following disclaimer.
12 // * Redistributions in binary form must reproduce the above copyright
13 // notice, this list of conditions and the following disclaimer in the
14 // documentation and/or other materials provided with the distribution.
15 // * Neither the name of Knut Reinert or the FU Berlin nor the names of
16 // its contributors may be used to endorse or promote products derived
17 // from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 // ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE
23 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
29 // DAMAGE.
30 //
31 // ==========================================================================
32 // Author: Rene Rahn <rene.rahn@fu-berlin.de>
33 // ==========================================================================
34 // The navigator for the sparse score dp-matrix. This class also provides an
35 // iterator for the active and the previous column. It stores the neighbouring
36 // cells needed for the recursion formula.
37 // ==========================================================================
38
39 #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_MATRIX_NAVIGATOR_SCORE_SPARSE_H_
40 #define SEQAN_INCLUDE_SEQAN_ALIGN_DP_MATRIX_NAVIGATOR_SCORE_SPARSE_H_
41
42 namespace seqan {
43
44 // ============================================================================
45 // Forwards
46 // ============================================================================
47
48 // ============================================================================
49 // Tags, Classes, Enums
50 // ============================================================================
51
52 // ----------------------------------------------------------------------------
53 // Class DPMatrixNavigator [SparseDPMatrix, ScoreMatrix]
54 // ----------------------------------------------------------------------------
55
56 // Specialization of the score matrix navigator for a sparse dp matrix.
57 template <typename TValue>
58 class DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise>
59 {
60 public:
61 typedef DPMatrix_<TValue, SparseDPMatrix> TDPMatrix_;
62 typedef typename Pointer_<TDPMatrix_>::Type TDPMatrixPointer_;
63 typedef typename Iterator<TDPMatrix_, Standard>::Type TDPMatrixIterator;
64
65 TDPMatrixPointer_ _ptrDataContainer; // Pointer to the underlying matrix to navigate on.
66 int _laneLeap; // The distance to leap when going to the next column.
67 TDPMatrixIterator _activeColIterator; // The iterator over the active column.
68 TDPMatrixIterator _prevColIterator; // The iterator over the previous column.
69 TValue _prevCellDiagonal; // The previous value in diagonal direction.
70 TValue _prevCellHorizontal; // The previous value in horizontal direction.
71 TValue _prevCellVertical; // The previous value in vertical direction.
72
73
74
DPMatrixNavigator_()75 DPMatrixNavigator_() :
76 _ptrDataContainer(TDPMatrixPointer_(0)),
77 _laneLeap(0),
78 _activeColIterator(),
79 _prevColIterator(),
80 _prevCellDiagonal(),
81 _prevCellHorizontal(),
82 _prevCellVertical()
83 {}
84 };
85
86 // ============================================================================
87 // Metafunctions
88 // ============================================================================
89
90 // ============================================================================
91 // Functions
92 // ============================================================================
93
94 // ----------------------------------------------------------------------------
95 // Function _init()
96 // ----------------------------------------------------------------------------
97
98
99 // Initializes the navigator for unbanded alignments
100 template <typename TValue>
101 inline void
_init(DPMatrixNavigator_<DPMatrix_<TValue,SparseDPMatrix>,DPScoreMatrix,NavigateColumnWise> & navigator,DPMatrix_<TValue,SparseDPMatrix> & dpMatrix,DPBandConfig<BandOff> const &)102 _init(DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise> & navigator,
103 DPMatrix_<TValue, SparseDPMatrix> & dpMatrix,
104 DPBandConfig<BandOff> const &)
105 {
106 navigator._ptrDataContainer = &dpMatrix;
107 navigator._activeColIterator = begin(dpMatrix, Standard());
108 navigator._prevColIterator = navigator._activeColIterator;
109 navigator._laneLeap = 1 - _dataLengths(dpMatrix)[DPMatrixDimension_::VERTICAL];
110 assignValue(navigator._activeColIterator, TValue());
111 }
112
113 // Initializes the navigator for banded alignments
114 template <typename TValue>
115 inline void
_init(DPMatrixNavigator_<DPMatrix_<TValue,SparseDPMatrix>,DPScoreMatrix,NavigateColumnWise> & navigator,DPMatrix_<TValue,SparseDPMatrix> & dpMatrix,DPBandConfig<BandOn> const & band)116 _init(DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise> & navigator,
117 DPMatrix_<TValue, SparseDPMatrix> & dpMatrix,
118 DPBandConfig<BandOn> const & band)
119 {
120 typedef DPMatrix_<TValue, SparseDPMatrix> TSparseDPMatrix;
121 typedef typename Size<TSparseDPMatrix>::Type TSize;
122 typedef typename MakeSigned<TSize>::Type TSignedSize;
123 navigator._ptrDataContainer = &dpMatrix;
124
125 // Band begins within the first row.
126 if (lowerDiagonal(band) >= 0)
127 {
128 navigator._laneLeap = 0;
129 navigator._activeColIterator = begin(dpMatrix, Standard()) + length(dpMatrix, DPMatrixDimension_::VERTICAL) - 1;
130 }
131 else if (upperDiagonal(band) <= 0) // Band begins within the first column
132 {
133 navigator._laneLeap = 1 - _dataLengths(dpMatrix)[DPMatrixDimension_::VERTICAL];
134 navigator._activeColIterator = begin(dpMatrix, Standard());
135 }
136 else // Band intersects with the point of origin.
137 {
138 navigator._laneLeap = _max(lowerDiagonal(band), 1 - static_cast<TSignedSize>(length(dpMatrix, DPMatrixDimension_::VERTICAL)));
139 navigator._activeColIterator = begin(dpMatrix, Standard()) + length(dpMatrix, DPMatrixDimension_::VERTICAL) + navigator._laneLeap - 1;
140 }
141 navigator._prevColIterator = navigator._activeColIterator;
142 assignValue(navigator._activeColIterator, TValue());
143 }
144
145 // ----------------------------------------------------------------------------
146 // Function _goNextCell() [DPInitialColumn, PartialColumnTop, FirstCell]
147 // ----------------------------------------------------------------------------
148
149 template <typename TValue>
150 inline void
_goNextCell(DPMatrixNavigator_<DPMatrix_<TValue,SparseDPMatrix>,DPScoreMatrix,NavigateColumnWise> &,MetaColumnDescriptor<DPInitialColumn,PartialColumnTop> const &,FirstCell const &)151 _goNextCell(DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise> & /*dpNavigator*/,
152 MetaColumnDescriptor<DPInitialColumn, PartialColumnTop> const &,
153 FirstCell const &)
154 {
155 // no-op
156 }
157
158 // ----------------------------------------------------------------------------
159 // Function _goNextCell() [DPInitialColumn, FullColumn, FirstCell]
160 // ----------------------------------------------------------------------------
161
162 template <typename TValue>
163 inline void
_goNextCell(DPMatrixNavigator_<DPMatrix_<TValue,SparseDPMatrix>,DPScoreMatrix,NavigateColumnWise> &,MetaColumnDescriptor<DPInitialColumn,FullColumn> const &,FirstCell const &)164 _goNextCell(DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise> & /*dpNavigator*/,
165 MetaColumnDescriptor<DPInitialColumn, FullColumn> const &,
166 FirstCell const &)
167 {
168 // no-op
169 }
170
171 // ----------------------------------------------------------------------------
172 // Function _goNextCell() [DPInitialColumn, FirstCell]
173 // ----------------------------------------------------------------------------
174
175 template <typename TValue, typename TColumnLocation>
176 inline void
_goNextCell(DPMatrixNavigator_<DPMatrix_<TValue,SparseDPMatrix>,DPScoreMatrix,NavigateColumnWise> &,MetaColumnDescriptor<DPInitialColumn,TColumnLocation> const &,FirstCell const &)177 _goNextCell(DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise> & /*dpNavigator*/,
178 MetaColumnDescriptor<DPInitialColumn, TColumnLocation> const &,
179 FirstCell const &)
180 {
181 // no-op
182 }
183
184 // ----------------------------------------------------------------------------
185 // Function _goNextCell() [PartialColumnTop, FirstCell]
186 // ----------------------------------------------------------------------------
187
188 template <typename TValue, typename TColumnType>
189 inline void
_goNextCell(DPMatrixNavigator_<DPMatrix_<TValue,SparseDPMatrix>,DPScoreMatrix,NavigateColumnWise> & dpNavigator,MetaColumnDescriptor<TColumnType,PartialColumnTop> const &,FirstCell const &)190 _goNextCell(DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise> & dpNavigator,
191 MetaColumnDescriptor<TColumnType, PartialColumnTop> const &,
192 FirstCell const &)
193 {
194 --dpNavigator._laneLeap;
195 dpNavigator._activeColIterator += dpNavigator._laneLeap;
196 dpNavigator._prevColIterator = dpNavigator._activeColIterator;
197 dpNavigator._prevCellHorizontal = value(++dpNavigator._prevColIterator);
198 }
199
200 // ----------------------------------------------------------------------------
201 // Function _goNextCell() [FullColumn, FirstCell]
202 // ----------------------------------------------------------------------------
203
204 template <typename TValue, typename TColumnType>
205 inline void
_goNextCell(DPMatrixNavigator_<DPMatrix_<TValue,SparseDPMatrix>,DPScoreMatrix,NavigateColumnWise> & dpNavigator,MetaColumnDescriptor<TColumnType,FullColumn> const &,FirstCell const &)206 _goNextCell(DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise> & dpNavigator,
207 MetaColumnDescriptor<TColumnType, FullColumn> const &,
208 FirstCell const &)
209 {
210 dpNavigator._activeColIterator += dpNavigator._laneLeap;
211 dpNavigator._prevCellHorizontal = value(dpNavigator._activeColIterator);
212 }
213
214 // ----------------------------------------------------------------------------
215 // Function _goNextCell() [FirstCell]
216 // ----------------------------------------------------------------------------
217
218 template <typename TValue, typename TColumnType, typename TColumnLocation>
219 inline void
_goNextCell(DPMatrixNavigator_<DPMatrix_<TValue,SparseDPMatrix>,DPScoreMatrix,NavigateColumnWise> & dpNavigator,MetaColumnDescriptor<TColumnType,TColumnLocation> const &,FirstCell const &)220 _goNextCell(DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise> & dpNavigator,
221 MetaColumnDescriptor<TColumnType, TColumnLocation> const &,
222 FirstCell const &)
223 {
224 dpNavigator._activeColIterator += dpNavigator._laneLeap;
225 dpNavigator._prevColIterator = dpNavigator._activeColIterator;
226 dpNavigator._prevCellDiagonal = value(dpNavigator._prevColIterator);
227 dpNavigator._prevCellHorizontal = value(++dpNavigator._prevColIterator);
228 }
229
230 // ----------------------------------------------------------------------------
231 // Function _goNextCell [DPInitialColumn, InnerCell]
232 // ----------------------------------------------------------------------------
233
234 template <typename TValue, typename TColumnLocation>
235 inline void
_goNextCell(DPMatrixNavigator_<DPMatrix_<TValue,SparseDPMatrix>,DPScoreMatrix,NavigateColumnWise> & dpNavigator,MetaColumnDescriptor<DPInitialColumn,TColumnLocation> const &,InnerCell const &)236 _goNextCell(DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise> & dpNavigator,
237 MetaColumnDescriptor<DPInitialColumn, TColumnLocation> const &,
238 InnerCell const &)
239 {
240 dpNavigator._prevCellVertical = value(dpNavigator._activeColIterator);
241 ++dpNavigator._activeColIterator;
242 }
243
244 // ----------------------------------------------------------------------------
245 // Function _goNextCell [DPInitialColumn, FullColumn, InnerCell]
246 // ----------------------------------------------------------------------------
247
248 template <typename TValue>
249 inline void
_goNextCell(DPMatrixNavigator_<DPMatrix_<TValue,SparseDPMatrix>,DPScoreMatrix,NavigateColumnWise> & dpNavigator,MetaColumnDescriptor<DPInitialColumn,FullColumn> const &,InnerCell const &)250 _goNextCell(DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise> & dpNavigator,
251 MetaColumnDescriptor<DPInitialColumn, FullColumn> const &,
252 InnerCell const &)
253 {
254 dpNavigator._prevCellVertical = value(dpNavigator._activeColIterator);
255 ++dpNavigator._activeColIterator;
256 }
257
258 // ----------------------------------------------------------------------------
259 // Function _goNextCell [InnerCell]
260 // ----------------------------------------------------------------------------
261
262 template <typename TValue, typename TColumnType, typename TColumnLocation>
263 inline void
_goNextCell(DPMatrixNavigator_<DPMatrix_<TValue,SparseDPMatrix>,DPScoreMatrix,NavigateColumnWise> & dpNavigator,MetaColumnDescriptor<TColumnType,TColumnLocation> const &,InnerCell const &)264 _goNextCell(DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise> & dpNavigator,
265 MetaColumnDescriptor<TColumnType, TColumnLocation> const &,
266 InnerCell const &)
267 {
268 dpNavigator._prevCellDiagonal = dpNavigator._prevCellHorizontal;
269 dpNavigator._prevCellVertical = value(dpNavigator._activeColIterator);
270 dpNavigator._prevCellHorizontal = value(++dpNavigator._prevColIterator);
271 ++dpNavigator._activeColIterator;
272 }
273
274 // ----------------------------------------------------------------------------
275 // Function _goNextCell [FullColumn, InnerCell]
276 // ----------------------------------------------------------------------------
277
278 template <typename TValue, typename TColumnType>
279 inline void
_goNextCell(DPMatrixNavigator_<DPMatrix_<TValue,SparseDPMatrix>,DPScoreMatrix,NavigateColumnWise> & dpNavigator,MetaColumnDescriptor<TColumnType,FullColumn> const &,InnerCell const &)280 _goNextCell(DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise> & dpNavigator,
281 MetaColumnDescriptor<TColumnType, FullColumn> const &,
282 InnerCell const &)
283 {
284 dpNavigator._prevCellDiagonal = dpNavigator._prevCellHorizontal;
285 dpNavigator._prevCellVertical = value(dpNavigator._activeColIterator);
286 dpNavigator._prevCellHorizontal = value(++dpNavigator._activeColIterator);
287 }
288
289 // ----------------------------------------------------------------------------
290 // Function _goNextCell [DPInitialColumn, LastCell]
291 // ----------------------------------------------------------------------------
292
293 template <typename TValue, typename TColumnLocation>
294 inline void
_goNextCell(DPMatrixNavigator_<DPMatrix_<TValue,SparseDPMatrix>,DPScoreMatrix,NavigateColumnWise> & dpNavigator,MetaColumnDescriptor<DPInitialColumn,TColumnLocation> const &,LastCell const &)295 _goNextCell(DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise> & dpNavigator,
296 MetaColumnDescriptor<DPInitialColumn, TColumnLocation> const &,
297 LastCell const &)
298 {
299 dpNavigator._prevCellVertical = value(dpNavigator._activeColIterator);
300 ++dpNavigator._activeColIterator;
301 }
302
303 // ----------------------------------------------------------------------------
304 // Function _goNextCell [DPInitialColumn, PartialColumnBottom, LastCell]
305 // ----------------------------------------------------------------------------
306
307 template <typename TValue>
308 inline void
_goNextCell(DPMatrixNavigator_<DPMatrix_<TValue,SparseDPMatrix>,DPScoreMatrix,NavigateColumnWise> & dpNavigator,MetaColumnDescriptor<DPInitialColumn,PartialColumnBottom> const &,LastCell const &)309 _goNextCell(DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise> & dpNavigator,
310 MetaColumnDescriptor<DPInitialColumn, PartialColumnBottom> const &,
311 LastCell const &)
312 {
313 dpNavigator._prevCellVertical = value(dpNavigator._activeColIterator);
314 ++dpNavigator._activeColIterator;
315 }
316
317 // ----------------------------------------------------------------------------
318 // Function _goNextCell [DPInitialColumn, FullColumn, LastCell]
319 // ----------------------------------------------------------------------------
320
321 template <typename TValue>
322 inline void
_goNextCell(DPMatrixNavigator_<DPMatrix_<TValue,SparseDPMatrix>,DPScoreMatrix,NavigateColumnWise> & dpNavigator,MetaColumnDescriptor<DPInitialColumn,FullColumn> const &,LastCell const &)323 _goNextCell(DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise> & dpNavigator,
324 MetaColumnDescriptor<DPInitialColumn, FullColumn> const &,
325 LastCell const &)
326 {
327 dpNavigator._prevCellVertical = value(dpNavigator._activeColIterator);
328 ++dpNavigator._activeColIterator;
329 }
330
331 // ----------------------------------------------------------------------------
332 // Function _goNextCell [LastCell]
333 // ----------------------------------------------------------------------------
334
335 template <typename TValue, typename TColumnType, typename TColumnLocation>
336 inline void
_goNextCell(DPMatrixNavigator_<DPMatrix_<TValue,SparseDPMatrix>,DPScoreMatrix,NavigateColumnWise> & dpNavigator,MetaColumnDescriptor<TColumnType,TColumnLocation> const &,LastCell const &)337 _goNextCell(DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise> & dpNavigator,
338 MetaColumnDescriptor<TColumnType, TColumnLocation> const &,
339 LastCell const &)
340 {
341 dpNavigator._prevCellDiagonal = dpNavigator._prevCellHorizontal;
342 dpNavigator._prevCellVertical = value(dpNavigator._activeColIterator);
343 ++dpNavigator._activeColIterator;
344 }
345
346 // ----------------------------------------------------------------------------
347 // Function _goNextCell [PartialColumnBottom, LastCell]
348 // ----------------------------------------------------------------------------
349
350 template <typename TValue, typename TColumnType>
351 inline void
_goNextCell(DPMatrixNavigator_<DPMatrix_<TValue,SparseDPMatrix>,DPScoreMatrix,NavigateColumnWise> & dpNavigator,MetaColumnDescriptor<TColumnType,PartialColumnBottom> const &,LastCell const &)352 _goNextCell(DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise> & dpNavigator,
353 MetaColumnDescriptor<TColumnType, PartialColumnBottom> const &,
354 LastCell const &)
355 {
356 dpNavigator._prevCellDiagonal = dpNavigator._prevCellHorizontal;
357 dpNavigator._prevCellVertical = value(dpNavigator._activeColIterator);
358 dpNavigator._prevCellHorizontal = value(++dpNavigator._prevColIterator);
359 ++dpNavigator._activeColIterator;
360 ++dpNavigator._laneLeap;
361 }
362
363 // ----------------------------------------------------------------------------
364 // Function _goNextCell [FullColumn, LastCell]
365 // ----------------------------------------------------------------------------
366
367
368 template <typename TValue, typename TColumnType>
369 inline void
_goNextCell(DPMatrixNavigator_<DPMatrix_<TValue,SparseDPMatrix>,DPScoreMatrix,NavigateColumnWise> & dpNavigator,MetaColumnDescriptor<TColumnType,FullColumn> const &,LastCell const &)370 _goNextCell(DPMatrixNavigator_<DPMatrix_<TValue, SparseDPMatrix>, DPScoreMatrix, NavigateColumnWise> & dpNavigator,
371 MetaColumnDescriptor<TColumnType, FullColumn> const &,
372 LastCell const &)
373 {
374 dpNavigator._prevCellDiagonal = dpNavigator._prevCellHorizontal;
375 dpNavigator._prevCellVertical = value(dpNavigator._activeColIterator);
376 dpNavigator._prevCellHorizontal = value(++dpNavigator._activeColIterator);
377 }
378
379 } // namespace seqan
380
381 #endif // #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_MATRIX_NAVIGATOR_SCORE_SPARSE_H_
382