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: Ren� Rahn <rene.rahn@fu-berlin.de>
33 // ==========================================================================
34 // This file implements the class DPMatrix and its specialization
35 // FullDPMatrix. The DPMatrix is a wrapper class around the Matrix<TValue,2>
36 // class. Thus we can implement different specializations for the dp-matrix
37 // that are used through the different dp-algorithms. For example, we need
38 // a full dp matrix to store the traceback or the score for the Waterman-
39 // Eggert algorithm, while for the other dp-algorithms we only need one
40 // column vector to compute the scores. The default dp-matrix specialization
41 // can be selected using a special meta-function.
42 // ==========================================================================
43 
44 // TODO(holtgrew): Documentation in this header necessary or internal only?
45 
46 #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_MATRIX_H_
47 #define SEQAN_INCLUDE_SEQAN_ALIGN_DP_MATRIX_H_
48 
49 namespace seqan {
50 
51 // ============================================================================
52 // Forwards
53 // ============================================================================
54 
55 template <typename TAlgorithm>
56 struct DefaultScoreMatrixSpec_;
57 
58 // ============================================================================
59 // Tags, Classes, Enums
60 // ============================================================================
61 
62 // ----------------------------------------------------------------------------
63 // Tag SparseDPMatrix
64 // ----------------------------------------------------------------------------
65 
66 struct SparseDPMatrix_;
67 typedef Tag<SparseDPMatrix_> SparseDPMatrix;
68 
69 // ----------------------------------------------------------------------------
70 // Tag FullDPMatrix
71 // ----------------------------------------------------------------------------
72 
73 struct FullDPMatrix_;
74 typedef Tag<FullDPMatrix_> FullDPMatrix;
75 
76 
77 // ----------------------------------------------------------------------------
78 // Enum DPMatrixDimension
79 // ----------------------------------------------------------------------------
80 
81 // Used to globally specify the correct dimension and the correct size of
82 // dimension for the dp matrix.
83 struct DPMatrixDimension_
84 {
85     typedef unsigned int TValue;
86 
87     static const TValue VERTICAL = 0u;
88     static const TValue HORIZONTAL = 1u;
89     static const TValue DIMENSION = 2u;
90 };
91 
92 // ----------------------------------------------------------------------------
93 // Class DPMatrix_
94 // ----------------------------------------------------------------------------
95 
96 // The dp matrix used as a score matrix and as a trace-back matrix.
97 template <typename TValue, typename TMatrixSpec>
98 class DPMatrix_
99 {};
100 
101 
102 // Default dp matrix implementation stores all cells of the dp matrix in the
103 // underlying two-dimensional matrix.
104 template <typename TValue>
105 class DPMatrix_<TValue, FullDPMatrix>
106 {
107 public:
108 
109     typedef Matrix<TValue, 2> THost;
110 
111     Holder<THost>   _dataHost;  // The host containing the actual matrix.
112 
DPMatrix_()113     DPMatrix_() :
114         _dataHost()
115     {
116         create(_dataHost);
117     }
118 
DPMatrix_(DPMatrix_ const & other)119     DPMatrix_(DPMatrix_ const & other) :
120         _dataHost(other._dataHost) {}
121 
~DPMatrix_()122     ~DPMatrix_() {}
123 
124     DPMatrix_ & operator=(DPMatrix_ const & other)
125     {
126         if (this != &other)
127         {
128             _dataHost = other._dataHost;
129         }
130         return *this;
131     }
132 
133 };
134 
135 // ============================================================================
136 // Metafunctions
137 // ============================================================================
138 
139 // ----------------------------------------------------------------------------
140 // Metafunction DefaultScoreMatrixSpec_
141 // ----------------------------------------------------------------------------
142 
143 // This meta-function determines the default specialization of dp matrix
144 // based on the given algorithm tag.
145 template <typename TAlgorithm>
146 struct DefaultScoreMatrixSpec_
147 {
148     typedef SparseDPMatrix Type;
149 };
150 
151 // TODO(rmaerker): Move to WatermanEggert implementation?
152 template <>
153 struct DefaultScoreMatrixSpec_<LocalAlignment_<WatermanEggert> >
154 {
155     typedef FullDPMatrix Type;
156 };
157 
158 // ----------------------------------------------------------------------------
159 // Metafunction DataHost_
160 // ----------------------------------------------------------------------------
161 
162 // Returns the type of the underlying matrix.
163 template <typename TDPMatrix>
164 struct DataHost_ {};
165 
166 template <typename TValue, typename TMatrixSpec>
167 struct DataHost_<DPMatrix_<TValue, TMatrixSpec> >
168 {
169     typedef DPMatrix_<TValue, TMatrixSpec> TDPMatrix_;
170     typedef typename TDPMatrix_::THost Type;
171 };
172 
173 template <typename TValue, typename TMatrixSpec>
174 struct DataHost_<DPMatrix_<TValue, TMatrixSpec> const>
175 {
176     typedef DPMatrix_<TValue, TMatrixSpec> TDPMatrix_;
177     typedef typename TDPMatrix_::THost const Type;
178 };
179 
180 // ----------------------------------------------------------------------------
181 // Metafunction SizeArr_
182 // ----------------------------------------------------------------------------
183 
184 // Returns the type of the containers to store the dimensions and the factors
185 // in order to move properly in the matrix.
186 template <typename TDPMatrix>
187 struct SizeArr_ {};
188 
189 template <typename TValue, typename TMatrixSpec>
190 struct SizeArr_<DPMatrix_<TValue, TMatrixSpec> >
191 {
192     typedef DPMatrix_<TValue, TMatrixSpec> TDPMatrix_;
193     typedef typename DataHost_<TDPMatrix_>::Type TDataHost_;
194     typedef typename SizeArr_<TDataHost_>::Type Type;
195 };
196 
197 template <typename TValue, typename TMatrixSpec>
198 struct SizeArr_<DPMatrix_<TValue, TMatrixSpec> const>
199 {
200     typedef DPMatrix_<TValue, TMatrixSpec> TDPMatrix_;
201     typedef typename DataHost_<TDPMatrix_>::Type TDataHost_;
202     typedef typename SizeArr_<TDataHost_>::Type const Type;
203 };
204 
205 // ----------------------------------------------------------------------------
206 // Metafunction Spec
207 // ----------------------------------------------------------------------------
208 
209 template <typename TValue, typename TMatrixSpec>
210 struct Spec<DPMatrix_<TValue, TMatrixSpec> >
211 {
212     typedef TMatrixSpec Type;
213 };
214 
215 template <typename TValue, typename TMatrixSpec>
216 struct Spec<DPMatrix_<TValue, TMatrixSpec> const>:
217     Spec<DPMatrix_<TValue, TMatrixSpec> >{};
218 
219 
220 // ----------------------------------------------------------------------------
221 // Metafunction Value
222 // ----------------------------------------------------------------------------
223 
224 template <typename TValue, typename TMatrixSpec>
225 struct Value<DPMatrix_<TValue, TMatrixSpec> >
226 {
227     typedef TValue Type;
228 };
229 
230 template <typename TValue, typename TMatrixSpec>
231 struct Value<DPMatrix_<TValue, TMatrixSpec> const>
232 {
233     typedef TValue const Type;
234 };
235 
236 // ----------------------------------------------------------------------------
237 // Metafunction Reference
238 // ----------------------------------------------------------------------------
239 
240 template <typename TValue, typename TMatrixSpec>
241 struct Reference<DPMatrix_<TValue, TMatrixSpec> >
242 {
243     typedef TValue & Type;
244 };
245 
246 template <typename TValue, typename TMatrixSpec>
247 struct Reference<DPMatrix_<TValue, TMatrixSpec> const>
248 {
249     typedef TValue const & Type;
250 };
251 
252 // ----------------------------------------------------------------------------
253 // Metafunction GetValue
254 // ----------------------------------------------------------------------------
255 
256 template <typename TValue, typename TMatrixSpec>
257 struct GetValue<DPMatrix_<TValue, TMatrixSpec> >:
258     Reference<DPMatrix_<TValue, TMatrixSpec> >{};
259 
260 template <typename TValue, typename TMatrixSpec>
261 struct GetValue<DPMatrix_<TValue, TMatrixSpec> const>:
262     Reference<DPMatrix_<TValue, TMatrixSpec> const>{};
263 
264 // ----------------------------------------------------------------------------
265 // Metafunction Position
266 // ----------------------------------------------------------------------------
267 
268 template <typename TValue, typename TMatrixSpec>
269 struct Position<DPMatrix_<TValue, TMatrixSpec> >
270 {
271     typedef typename DPMatrix_<TValue, TMatrixSpec>::THost TDataMatrix_;
272     typedef typename Position<TDataMatrix_>::Type Type;
273 };
274 
275 template <typename TValue, typename TMatrixSpec>
276 struct Position<DPMatrix_<TValue, TMatrixSpec> const>:
277     Position<DPMatrix_<TValue, TMatrixSpec> >{};
278 
279 // ----------------------------------------------------------------------------
280 // Metafunction Size
281 // ----------------------------------------------------------------------------
282 
283 template <typename TValue, typename TMatrixSpec>
284 struct Size<DPMatrix_<TValue, TMatrixSpec> >
285 {
286     typedef typename DPMatrix_<TValue, TMatrixSpec>::THost TDataMatrix_;
287     typedef typename Size<TDataMatrix_>::Type Type;
288 };
289 
290 template <typename TValue, typename TMatrixSpec>
291 struct Size<DPMatrix_<TValue, TMatrixSpec> const>:
292     Size<DPMatrix_<TValue, TMatrixSpec> >{};
293 
294 // ----------------------------------------------------------------------------
295 // Metafunction Host
296 // ----------------------------------------------------------------------------
297 
298 template <typename TValue, typename TMatrixSpec>
299 struct Host<DPMatrix_<TValue, TMatrixSpec> >
300 {
301     typedef DPMatrix_<TValue, TMatrixSpec> TDPMatrix_;
302     typedef typename DataHost_<TDPMatrix_>::Type TDataMatrix_;
303     typedef typename Host<TDataMatrix_>::Type Type;
304 };
305 
306 template <typename TValue, typename TMatrixSpec>
307 struct Host<DPMatrix_<TValue, TMatrixSpec> const>
308 {
309     typedef DPMatrix_<TValue, TMatrixSpec> TDPMatrix_;
310     typedef typename DataHost_<TDPMatrix_>::Type TDataMatrix_;
311     typedef typename Host<TDataMatrix_>::Type const Type;
312 };
313 
314 // ----------------------------------------------------------------------------
315 // Metafunction Iterator
316 // ----------------------------------------------------------------------------
317 
318 // There are two iterator types. The standard iterator returns a
319 // non-rooted iterator to the underlying vector of the hosted two-dimensional
320 // matrix. The rooted iterator returns the iterator defined by the
321 // hosted matrix object which is a position iterator.
322 template <typename TValue, typename TMatrixSpec>
323 struct Iterator<DPMatrix_<TValue, TMatrixSpec>, Standard const>
324 {
325     typedef DPMatrix_<TValue, TMatrixSpec> TDPMatrix_;
326     typedef typename  Host<TDPMatrix_>::Type THost_;
327     typedef typename Iterator<THost_, Standard>::Type Type;
328 };
329 
330 template <typename TValue, typename TMatrixSpec>
331 struct Iterator<DPMatrix_<TValue, TMatrixSpec> const, Standard const>
332 {
333     typedef DPMatrix_<TValue, TMatrixSpec> const TDPMatrix_;
334     typedef typename  Host<TDPMatrix_>::Type THost_;
335     typedef typename Iterator<THost_ const, Standard>::Type Type;
336 };
337 
338 template <typename TValue, typename TMatrixSpec>
339 struct Iterator<DPMatrix_<TValue, TMatrixSpec>, Rooted const>
340 {
341     typedef DPMatrix_<TValue, TMatrixSpec> TDPMatrix_;
342     typedef typename  DataHost_<TDPMatrix_>::Type TDataMatrix_;
343     typedef typename Iterator<TDataMatrix_, Rooted>::Type Type;
344 };
345 
346 template <typename TValue, typename TMatrixSpec>
347 struct Iterator<DPMatrix_<TValue, TMatrixSpec> const, Rooted const>
348 {
349     typedef DPMatrix_<TValue, TMatrixSpec> TDPMatrix_;
350     typedef typename  DataHost_<TDPMatrix_>::Type TDataMatrix_;
351     typedef typename Iterator<TDataMatrix_ const, Rooted>::Type Type;
352 };
353 
354 // ============================================================================
355 // Functions
356 // ============================================================================
357 
358 // ----------------------------------------------------------------------------
359 // Function _checkCorrectDimension()
360 // ----------------------------------------------------------------------------
361 
362 // Checks whether a given value applies to the correct dimension.
363 inline bool _checkCorrectDimension(DPMatrixDimension_::TValue dim)
364 {
365     return dim < DPMatrixDimension_::DIMENSION;
366 }
367 
368 // ----------------------------------------------------------------------------
369 // Function _dataHost()
370 // ----------------------------------------------------------------------------
371 
372 // Returns a reference to the hosted matrix.
373 template <typename TValue, typename TMatrixSpec>
374 inline typename DataHost_<DPMatrix_<TValue, TMatrixSpec> >::Type &
375 _dataHost(DPMatrix_<TValue, TMatrixSpec>&dpMatrix)
376 {
377     return value(dpMatrix._dataHost);
378 }
379 
380 template <typename TValue, typename TMatrixSpec>
381 inline typename DataHost_<DPMatrix_<TValue, TMatrixSpec> const>::Type &
382 _dataHost(DPMatrix_<TValue, TMatrixSpec> const & dpMatrix)
383 {
384     return value(dpMatrix._dataHost);
385 }
386 
387 // ----------------------------------------------------------------------------
388 // Function _dataLengths()
389 // ----------------------------------------------------------------------------
390 
391 // Returns a reference to the _dataLengths container of the hosted matrix.
392 template <typename TValue, typename TMatrixSpec>
393 inline typename SizeArr_<DPMatrix_<TValue, TMatrixSpec> >::Type &
394 _dataLengths(DPMatrix_<TValue, TMatrixSpec>&dpMatrix)
395 {
396     return _dataLengths(_dataHost(dpMatrix));
397 }
398 
399 template <typename TValue, typename TMatrixSpec>
400 inline typename SizeArr_<DPMatrix_<TValue, TMatrixSpec> const>::Type &
401 _dataLengths(DPMatrix_<TValue, TMatrixSpec> const & dpMatrix)
402 {
403     return _dataLengths(_dataHost(dpMatrix));
404 }
405 
406 // ----------------------------------------------------------------------------
407 // Function _dataFactors()
408 // ----------------------------------------------------------------------------
409 
410 // Returns a reference to the _dataFactors container of the hosted matrix.
411 template <typename TValue, typename TMatrixSpec>
412 inline typename SizeArr_<DPMatrix_<TValue, TMatrixSpec> >::Type &
413 _dataFactors(DPMatrix_<TValue, TMatrixSpec>&dpMatrix)
414 {
415     return _dataFactors(_dataHost(dpMatrix));
416 }
417 
418 template <typename TValue, typename TMatrixSpec>
419 inline typename SizeArr_<DPMatrix_<TValue, TMatrixSpec> const>::Type &
420 _dataFactors(DPMatrix_<TValue, TMatrixSpec> const & dpMatrix)
421 {
422     return _dataFactors(_dataHost(dpMatrix));
423 }
424 
425 // ----------------------------------------------------------------------------
426 // Function host()
427 // ----------------------------------------------------------------------------
428 
429 // Returns a reference to the underlying vector of the hosted matrix.
430 template <typename TValue, typename TMatrixSpec>
431 inline typename Host<DPMatrix_<TValue, TMatrixSpec> >::Type &
432 host(DPMatrix_<TValue, TMatrixSpec>&dpMatrix)
433 {
434     return host(_dataHost(dpMatrix));
435 }
436 
437 template <typename TValue, typename TMatrixSpec>
438 inline typename Host<DPMatrix_<TValue, TMatrixSpec> const>::Type &
439 host(DPMatrix_<TValue, TMatrixSpec> const & dpMatrix)
440 {
441     return host(_dataHost(dpMatrix));
442 }
443 
444 // ----------------------------------------------------------------------------
445 // Function setHost()
446 // ----------------------------------------------------------------------------
447 
448 // Sets a new value to the underlying vector of the hosted matrix.
449 template <typename TValue, typename TMatrixSpec, typename THost>
450 inline void
451 setHost(DPMatrix_<TValue, TMatrixSpec> & dpMatrix,
452         THost & newHost)
453 {
454     setHost(_dataHost(dpMatrix), newHost);
455 }
456 
457 template <typename TValue, typename TMatrixSpec, typename THost>
458 inline void
459 setHost(DPMatrix_<TValue, TMatrixSpec> & dpMatrix,
460         THost const & newHost)
461 {
462     setHost(_dataHost(dpMatrix), newHost);
463 }
464 
465 // ----------------------------------------------------------------------------
466 // Function value()
467 // ----------------------------------------------------------------------------
468 
469 // Returns the value of the matrix at the given host position.
470 template <typename TValue, typename TMatrixSpec, typename TPosition>
471 inline typename Reference<DPMatrix_<TValue, TMatrixSpec> >::Type
472 value(DPMatrix_<TValue, TMatrixSpec> & dpMatrix,
473       TPosition const & pos)
474 {
475     return value(_dataHost(dpMatrix), pos);
476 }
477 
478 template <typename TValue, typename TMatrixSpec, typename TPosition>
479 inline typename Reference<DPMatrix_<TValue, TMatrixSpec> const>::Type
480 value(DPMatrix_<TValue, TMatrixSpec> const & dpMatrix,
481       TPosition const & pos)
482 {
483     return value(_dataHost(dpMatrix), pos);
484 }
485 
486 // Returns the value of the matrix at the two given coordinates.
487 template <typename TValue, typename TMatrixSpec, typename TPositionV, typename TPositionH>
488 inline typename Reference<DPMatrix_<TValue, TMatrixSpec> >::Type
489 value(DPMatrix_<TValue, TMatrixSpec> & dpMatrix,
490       TPositionV const & posDimV,
491       TPositionH const & posDimH)
492 {
493     return value(_dataHost(dpMatrix), posDimV, posDimH);
494 }
495 
496 template <typename TValue, typename TMatrixSpec, typename TPositionV, typename TPositionH>
497 inline typename Reference<DPMatrix_<TValue, TMatrixSpec> const>::Type
498 value(DPMatrix_<TValue, TMatrixSpec> const & dpMatrix,
499       TPositionV const & posDimV,
500       TPositionH const & posDimH)
501 {
502     return value(_dataHost(dpMatrix), posDimV, posDimH);
503 }
504 
505 // ----------------------------------------------------------------------------
506 // Function length()
507 // ----------------------------------------------------------------------------
508 
509 // Returns the length of a given dimension.
510 template <typename TValue, typename TMatrixSpec>
511 inline typename Size<DPMatrix_<TValue, TMatrixSpec> const>::Type
512 length(DPMatrix_<TValue, TMatrixSpec> const & dpMatrix,
513        unsigned int dimension)
514 {
515     SEQAN_ASSERT(_checkCorrectDimension(dimension));
516 
517     return length(_dataHost(dpMatrix), dimension);
518 }
519 
520 // Returns the overall length of the underlying vector of the hosted matrix.
521 template <typename TValue, typename TMatrixSpec>
522 inline typename Size<DPMatrix_<TValue, TMatrixSpec> const>::Type
523 length(DPMatrix_<TValue, TMatrixSpec> const & dpMatrix)
524 {
525     return length(_dataHost(dpMatrix));  // Note that even if the dimensional lengths are set but the matrix was not resized
526     // this function returns 0 or the previous length of the host before the resize.
527 }
528 
529 // ----------------------------------------------------------------------------
530 // Function clear()
531 // ----------------------------------------------------------------------------
532 
533 template <typename TValue, typename TMatrixSpec>
534 inline void
535 clear(DPMatrix_<TValue, TMatrixSpec> & dpMatrix)
536 {
537     clear(_dataLengths(dpMatrix));
538     resize(_dataLengths(dpMatrix), 2, 0);
539     clear(_dataFactors(dpMatrix));
540     resize(_dataFactors(dpMatrix), 2, 0);
541     _dataFactors(dpMatrix)[DPMatrixDimension_::VERTICAL] = 1u;
542     clear(host(dpMatrix));
543 }
544 
545 // ----------------------------------------------------------------------------
546 // Function empty()
547 // ----------------------------------------------------------------------------
548 
549 template <typename TValue, typename TMatrixSpec>
550 inline bool
551 empty(DPMatrix_<TValue, TMatrixSpec> const & dpMatrix)
552 {
553     return empty(host(dpMatrix));
554 }
555 
556 // ----------------------------------------------------------------------------
557 // Function setLength()
558 // ----------------------------------------------------------------------------
559 
560 // Sets the new length of a given dimension.
561 template <typename TValue, typename TMatrixSpec, typename TSize>
562 inline void
563 setLength(DPMatrix_<TValue, TMatrixSpec> & dpMatrix,
564           unsigned int dimension,
565           TSize const & newLength)
566 {
567     SEQAN_ASSERT(_checkCorrectDimension(dimension));
568     setLength(_dataHost(dpMatrix), dimension, newLength);
569 }
570 
571 // ----------------------------------------------------------------------------
572 // Function updateFactors()
573 // ----------------------------------------------------------------------------
574 
575 template <typename TValue, typename TMatrixSpec>
576 inline typename Size<DPMatrix_<TValue, TMatrixSpec> >::Type
577 updateFactors(DPMatrix_<TValue, TMatrixSpec> & dpMatrix)
578 {
579     typedef typename Size<DPMatrix_<TValue, TMatrixSpec> >::Type TSize;
580 
581     TSize factor_ = _dataFactors(dpMatrix)[0] * length(dpMatrix, 0);
582     for (unsigned int i = 1; (factor_ > 0) && (i < dimension(_dataHost(dpMatrix))); ++i)
583     {
584         _dataFactors(dpMatrix)[i] = factor_;
585         factor_ *= length(dpMatrix, i);
586     }
587     return factor_;
588 }
589 
590 // ----------------------------------------------------------------------------
591 // Function resize()
592 // ----------------------------------------------------------------------------
593 
594 // Resizes the matrix. Note, the lengths of the dimensions have to be set before.
595 template <typename TValue, typename TMatrixSpec>
596 inline void
597 resize(DPMatrix_<TValue, TMatrixSpec> & dpMatrix)
598 {
599     typedef typename Size<DPMatrix_<TValue, TMatrixSpec> >::Type TSize;
600 
601     TSize reqSize = updateFactors(dpMatrix);
602     if (reqSize >= length(dpMatrix))
603         resize(host(dpMatrix), reqSize, Exact());
604 }
605 
606 template <typename TValue, typename TMatrixSpec>
607 inline void
608 resize(DPMatrix_<TValue, TMatrixSpec> & dpMatrix,
609        TValue const & fillValue)
610 {
611     typedef typename Size<DPMatrix_<TValue, TMatrixSpec> >::Type TSize;
612 
613     TSize reqSize = updateFactors(dpMatrix);
614     if (reqSize >= length(dpMatrix))
615         resize(host(dpMatrix), reqSize, fillValue, Exact());
616 }
617 
618 // ----------------------------------------------------------------------------
619 // Function begin()
620 // ----------------------------------------------------------------------------
621 
622 template <typename TValue, typename TMatrixSpec>
623 inline typename Iterator<DPMatrix_<TValue, TMatrixSpec>, Standard const>::Type
624 begin(DPMatrix_<TValue, TMatrixSpec> & dpMatrix, Standard const)
625 {
626     return begin(host(dpMatrix));
627 }
628 
629 template <typename TValue, typename TMatrixSpec>
630 inline typename Iterator<DPMatrix_<TValue, TMatrixSpec> const, Standard const>::Type
631 begin(DPMatrix_<TValue, TMatrixSpec> const & dpMatrix, Standard const)
632 {
633     return begin(host(dpMatrix));
634 }
635 
636 template <typename TValue, typename TMatrixSpec>
637 inline typename Iterator<DPMatrix_<TValue, TMatrixSpec>, Rooted const>::Type
638 begin(DPMatrix_<TValue, TMatrixSpec> & dpMatrix, Rooted const)
639 {
640     return begin(_dataHost(dpMatrix));
641 }
642 
643 template <typename TValue, typename TMatrixSpec>
644 inline typename Iterator<DPMatrix_<TValue, TMatrixSpec> const, Rooted const>::Type
645 begin(DPMatrix_<TValue, TMatrixSpec> const & dpMatrix, Rooted const)
646 {
647     return begin(_dataHost(dpMatrix));
648 }
649 
650 // ----------------------------------------------------------------------------
651 // Function end()
652 // ----------------------------------------------------------------------------
653 
654 template <typename TValue, typename TMatrixSpec>
655 inline typename Iterator<DPMatrix_<TValue, TMatrixSpec>, Standard const>::Type
656 end(DPMatrix_<TValue, TMatrixSpec> & dpMatrix, Standard const)
657 {
658     return end(host(dpMatrix));
659 }
660 
661 template <typename TValue, typename TMatrixSpec>
662 inline typename Iterator<DPMatrix_<TValue, TMatrixSpec> const, Standard const>::Type
663 end(DPMatrix_<TValue, TMatrixSpec> const & dpMatrix, Standard const)
664 {
665     return end(host(dpMatrix));
666 }
667 
668 template <typename TValue, typename TMatrixSpec>
669 inline typename Iterator<DPMatrix_<TValue, TMatrixSpec>, Rooted const>::Type
670 end(DPMatrix_<TValue, TMatrixSpec> & dpMatrix, Rooted const)
671 {
672     return end(_dataHost(dpMatrix));
673 }
674 
675 template <typename TValue, typename TMatrixSpec>
676 inline typename Iterator<DPMatrix_<TValue, TMatrixSpec> const, Rooted const>::Type
677 end(DPMatrix_<TValue, TMatrixSpec> const & dpMatrix, Rooted const)
678 {
679     return end(_dataHost(dpMatrix));
680 }
681 
682 // ----------------------------------------------------------------------------
683 // Function coordinate()
684 // ----------------------------------------------------------------------------
685 
686 // Returns the coordinate of a host positio in a given dimension.
687 template <typename TValue, typename TPosition>
688 inline typename Position<DPMatrix_<TValue, FullDPMatrix> >::Type
689 coordinate(DPMatrix_<TValue, FullDPMatrix> const & dpMatrix,
690            TPosition hostPos,
691            typename DPMatrixDimension_::TValue dimension)
692 {
693     return coordinate(_dataHost(dpMatrix), hostPos, dimension);
694 }
695 
696 } // namespace seqan
697 
698 #endif  // #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_MATRIX_H_
699