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 // Implements the DPMatrixNavigator. 35 // This is the parent class for all navigators that parse over a dp-matrix. 36 // This class facilitates the correct navigation through the dp-matrix for 37 // all kind of standard dp-algorithms. At the moment there only exists the 38 // NavigateColumnWise but this can be complemented by other navigation 39 // structures like anti-diagonals or in tiles. 40 // The Navigator can be specialized with three parameters. The first one is 41 // the used specialization of the dp-matrix (FullDPMatrix or SparseDPMatrix). 42 // the second parameter decides if it is a navigator for a score matrix or 43 // a trace matrix. And the last parameter determines the sort of navigation. 44 // ========================================================================== 45 46 // TODO(holtgrew): Documentation in this header necessary or internal only? 47 48 #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_MATRIX_NAVIGATOR_H_ 49 #define SEQAN_INCLUDE_SEQAN_ALIGN_DP_MATRIX_NAVIGATOR_H_ 50 51 namespace seqan { 52 53 // ============================================================================ 54 // Forwards 55 // ============================================================================ 56 57 // ============================================================================ 58 // Tags, Classes, Enums 59 // ============================================================================ 60 61 // ---------------------------------------------------------------------------- 62 // Tag DPScoreMatrix 63 // ---------------------------------------------------------------------------- 64 65 // Used to select a navigator for the score matrix. 66 struct DPScoreMatrix_; 67 typedef Tag<DPScoreMatrix_> DPScoreMatrix; 68 69 // ---------------------------------------------------------------------------- 70 // Tag DPTraceMatrix 71 // ---------------------------------------------------------------------------- 72 73 // Used to select a navigator for the trace matrix. 74 template <typename TTraceFlag> 75 struct DPTraceMatrix {}; 76 77 // ---------------------------------------------------------------------------- 78 // Tag NavigateColumnWise 79 // ---------------------------------------------------------------------------- 80 81 // Facilitates column wise navigation through the dp-matrix. 82 struct NavigateColumnWise_; 83 typedef Tag<NavigateColumnWise_> NavigateColumnWise; 84 85 // ---------------------------------------------------------------------------- 86 // Class DPMatrixNavigator_ 87 // ---------------------------------------------------------------------------- 88 89 template <typename TDPMatrix, typename TDPMatrixType, typename TNavigationSpec = NavigateColumnWise> 90 class DPMatrixNavigator_; 91 92 // ============================================================================ 93 // Metafunctions 94 // ============================================================================ 95 96 // ---------------------------------------------------------------------------- 97 // Metafunction Value 98 // ---------------------------------------------------------------------------- 99 100 template <typename TDPMatrix, typename TDPMatrixType, typename TNavigationSpec> 101 struct Value<DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> > 102 { 103 typedef typename Value<TDPMatrix>::Type Type; 104 }; 105 106 template <typename TDPMatrix, typename TDPMatrixType, typename TNavigationSpec> 107 struct Value<DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> const> 108 { 109 typedef typename Value<TDPMatrix const>::Type Type; 110 }; 111 112 // ---------------------------------------------------------------------------- 113 // Metafunction Reference 114 // ---------------------------------------------------------------------------- 115 116 template <typename TDPMatrix, typename TDPMatrixType, typename TNavigationSpec> 117 struct Reference<DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> > 118 { 119 typedef typename Reference<TDPMatrix>::Type Type; 120 }; 121 122 template <typename TDPMatrix, typename TDPMatrixType, typename TNavigationSpec> 123 struct Reference<DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> const> 124 { 125 typedef typename Reference<TDPMatrix const>::Type Type; 126 }; 127 128 // ---------------------------------------------------------------------------- 129 // Metafunction Container 130 // ---------------------------------------------------------------------------- 131 132 template <typename TDPMatrix, typename TDPMatrixType, typename TNavigationSpec> 133 struct Container<DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> > 134 { 135 typedef TDPMatrix Type; 136 }; 137 138 template <typename TDPMatrix, typename TDPMatrixType, typename TNavigationSpec> 139 struct Container<DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> const> 140 { 141 typedef TDPMatrix const Type; 142 }; 143 144 // ============================================================================ 145 // Functions 146 // ============================================================================ 147 148 // ---------------------------------------------------------------------------- 149 // Function assignValue() 150 // ---------------------------------------------------------------------------- 151 152 template <typename TDPMatrix, typename TDPMatrixType, typename TNavigationSpec, typename TValue> 153 inline void 154 assignValue(DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> & dpNavigator, 155 TValue const & element) 156 { 157 assignValue(dpNavigator._activeColIterator, element); 158 } 159 160 // ---------------------------------------------------------------------------- 161 // Function value() 162 // ---------------------------------------------------------------------------- 163 164 template <typename TDPMatrix, typename TDPMatrixType, typename TNavigationSpec> 165 inline typename Reference<DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> >::Type 166 value(DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> & dpNavigator) 167 { 168 return value(dpNavigator._activeColIterator); 169 } 170 171 template <typename TDPMatrix, typename TDPMatrixType, typename TNavigationSpec> 172 inline typename Reference<DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> const>::Type 173 value(DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> const & dpNavigator) 174 { 175 return value(dpNavigator._activeColIterator); 176 } 177 178 template <typename TDPMatrix, typename TDPMatrixType, typename TNavigationSpec, typename TCoordinateV, typename TCoordinateH> 179 inline typename Reference<DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> >::Type 180 value(DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> & dpNavigator, 181 TCoordinateH const & coordinateV, 182 TCoordinateV const & coordinateH) 183 { 184 return value(container(dpNavigator), coordinateV, coordinateH); 185 } 186 187 template <typename TDPMatrix, typename TDPMatrixType, typename TNavigationSpec, typename TCoordinateV, typename TCoordinateH> 188 inline typename Reference<DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> const>::Type 189 value(DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> const & dpNavigator, 190 TCoordinateV const & coordinateV, 191 TCoordinateH const & coordinateH) 192 { 193 return value(container(dpNavigator), coordinateV, coordinateH); 194 } 195 196 // ---------------------------------------------------------------------------- 197 // Function coordinate() 198 // ---------------------------------------------------------------------------- 199 200 template <typename TDPMatrix, typename TDPMatrixType, typename TNavigationSpec> 201 inline typename DPMatrixDimension_::TValue 202 coordinate(DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> const & dpNavigator, 203 typename DPMatrixDimension_::TValue const & dimension) 204 { 205 // Simply delegate to coordinate of underlying matrix. 206 return coordinate(value(dpNavigator._ptrDataContainer), 207 dpNavigator._activeColIterator - begin(*dpNavigator._ptrDataContainer, Standard()), dimension); 208 } 209 210 // ---------------------------------------------------------------------------- 211 // Function container() 212 // ---------------------------------------------------------------------------- 213 214 template <typename TDPMatrix, typename TDPMatrixType, typename TNavigationSpec> 215 inline typename Container<DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> >::Type & 216 container(DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> & dpNavigator) 217 { 218 return *dpNavigator._ptrDataContainer; 219 } 220 221 template <typename TDPMatrix, typename TDPMatrixType, typename TNavigationSpec> 222 inline typename Container<DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> const>::Type & 223 container(DPMatrixNavigator_<TDPMatrix, TDPMatrixType, TNavigationSpec> const & dpNavigator) 224 { 225 return *dpNavigator._ptrDataContainer; 226 } 227 228 } // namespace seqan 229 230 #endif // #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_MATRIX_NAVIGATOR_H_ 231