1 // ==========================================================================
2 //                 SeqAn - The Library for Sequence Analysis
3 // ==========================================================================
4 // Copyright (c) 2006-2018, 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 //
35 // The TraceSegment structure is used to store the traceback in a common
36 // structure such that we can easiely adapt them afterwards in the
37 // user-defined structure, such as Align or AlignmentGraph objects.
38 // ==========================================================================
39 
40 #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_TRACE_SEGMENT_H_
41 #define SEQAN_INCLUDE_SEQAN_ALIGN_DP_TRACE_SEGMENT_H_
42 
43 namespace seqan {
44 
45 // ============================================================================
46 // Forwards
47 // ============================================================================
48 
49 // ============================================================================
50 // Tags, Classes, Enums
51 // ============================================================================
52 
53 // ----------------------------------------------------------------------------
54 // Class TraceSegment
55 // ----------------------------------------------------------------------------
56 
57 // TraceSegments are used as a common interface to all structures that can represent an alignment.
58 //
59 // See alignment_dp_traceback_adaptor.h to find methods for adaption.
60 template <typename TPosition, typename TSize>
61 class TraceSegment_
62 {
63 public:
64     typedef typename TraceBitMap_<>::Type TTraceValue;
65 
66     TPosition _horizontalBeginPos;      // the begin position in horizontal dimension
67     TPosition _verticalBeginPos;        // the begin position in vertical dimension
68     TSize _length;                      // the length of the segment
69     TTraceValue _traceValue;            // the trace direction
70 
TraceSegment_()71     TraceSegment_() :
72         _horizontalBeginPos(0), _verticalBeginPos(0), _length(0), _traceValue(TraceBitMap_<TTraceValue>::NONE){}
73 
TraceSegment_(TraceSegment_ const & other)74     TraceSegment_(TraceSegment_ const & other) :
75         _horizontalBeginPos(other._horizontalBeginPos),
76         _verticalBeginPos(other._verticalBeginPos),
77         _length(other._length),
78         _traceValue(other._traceValue) {}
79 
TraceSegment_(TPosition const & horizontalBeginPos,TPosition const & verticalBeginPos,TSize const & length,TTraceValue const & traceValue)80     TraceSegment_(TPosition const & horizontalBeginPos, TPosition const & verticalBeginPos, TSize const & length,
81                   TTraceValue const & traceValue) :
82         _horizontalBeginPos(horizontalBeginPos),
83         _verticalBeginPos(verticalBeginPos),
84         _length(length),
85         _traceValue(traceValue) {}
86 
87     TraceSegment_ &
88     operator=(TraceSegment_ const & other)
89     {
90         if (this != &other)
91         {
92             _horizontalBeginPos = other._horizontalBeginPos;
93             _verticalBeginPos = other._verticalBeginPos;
94             _length = other._length;
95             _traceValue = other._traceValue;
96         }
97         return *this;
98     }
99 
100 };
101 
102 
103 // ============================================================================
104 // Metafunctions
105 // ============================================================================
106 
107 // ----------------------------------------------------------------------------
108 // Metafunction Position
109 // ----------------------------------------------------------------------------
110 
111 template <typename TPosition, typename TSize>
112 struct Position<TraceSegment_<TPosition, TSize> >
113 {
114     typedef TPosition Type;
115 };
116 
117 template <typename TPosition, typename TSize>
118 struct Position<TraceSegment_<TPosition, TSize> const>:
119     Position<TraceSegment_<TPosition, TSize> >{};
120 
121 // ----------------------------------------------------------------------------
122 // Metafunction Size
123 // ----------------------------------------------------------------------------
124 
125 template <typename TPosition, typename TSize>
126 struct Size<TraceSegment_<TPosition, TSize> >
127 {
128     typedef TSize Type;
129 };
130 
131 template <typename TPosition, typename TSize>
132 struct Size<TraceSegment_<TPosition, TSize> const>:
133     Size<TraceSegment_<TPosition, TSize> >{};
134 
135 // ============================================================================
136 // Functions
137 // ============================================================================
138 
139 // ----------------------------------------------------------------------------
140 // Function _getBeginHorizontal()
141 // ----------------------------------------------------------------------------
142 
143 // The begin position of the segment in horizontal dimension.
144 template <typename TPosition, typename TSize>
145 inline TPosition
146 _getBeginHorizontal(TraceSegment_<TPosition, TSize> const & traceSegment)
147 {
148     return traceSegment._horizontalBeginPos;
149 }
150 
151 // ----------------------------------------------------------------------------
152 // Function _getBeginVertical()
153 // ----------------------------------------------------------------------------
154 
155 // The begin position of the segment in vertical dimension.
156 template <typename TPosition, typename TSize>
157 inline TPosition
158 _getBeginVertical(TraceSegment_<TPosition, TSize> const & traceSegment)
159 {
160     return traceSegment._verticalBeginPos;
161 }
162 
163 // ----------------------------------------------------------------------------
164 // Function _getEndHorizontal()
165 // ----------------------------------------------------------------------------
166 
167 // The end position of the segment in horizontal dimension.
168 template <typename TPosition, typename TSize>
169 inline TPosition
170 _getEndHorizontal(TraceSegment_<TPosition, TSize> const & traceSegment)
171 {
172     typedef typename std::remove_const<decltype(traceSegment._traceValue)>::type TTraceValue;
173     if (traceSegment._traceValue & (TraceBitMap_<TTraceValue>::HORIZONTAL | TraceBitMap_<TTraceValue>::DIAGONAL))
174     {
175         return traceSegment._horizontalBeginPos + traceSegment._length;
176     }
177     return traceSegment._horizontalBeginPos;
178 }
179 
180 // ----------------------------------------------------------------------------
181 // Function _getEndVertical()
182 // ----------------------------------------------------------------------------
183 
184 // The end position of the segment in vertical dimension.
185 template <typename TPosition, typename TSize>
186 inline TPosition
187 _getEndVertical(TraceSegment_<TPosition, TSize> const & traceSegment)
188 {
189     typedef typename std::remove_const<decltype(traceSegment._traceValue)>::type TTraceValue;
190     if (traceSegment._traceValue & (TraceBitMap_<TTraceValue>::VERTICAL | TraceBitMap_<TTraceValue>::DIAGONAL))
191     {
192         return traceSegment._verticalBeginPos + traceSegment._length;
193     }
194     return traceSegment._verticalBeginPos;
195 }
196 
197 // ----------------------------------------------------------------------------
198 // Function _getTraceValue()
199 // ----------------------------------------------------------------------------
200 
201 // The end position of the segment in vertical dimension.
202 template <typename TPosition, typename TSize>
203 inline typename TraceSegment_<TPosition, TSize>::TTraceValue
204 _getTraceValue(TraceSegment_<TPosition, TSize> const & traceSegment)
205 {
206     return traceSegment._traceValue;
207 }
208 
209 // ----------------------------------------------------------------------------
210 // Function length()
211 // ----------------------------------------------------------------------------
212 
213 // The length of the segment.
214 template <typename TPosition, typename TSize>
215 inline TSize
216 length(TraceSegment_<TPosition, TSize> const & traceSegment)
217 {
218     return traceSegment._length;
219 }
220 
221 // ----------------------------------------------------------------------------
222 // Function _setLength()
223 // ----------------------------------------------------------------------------
224 
225 // The length of the segment.
226 template <typename TPosition, typename TSize>
227 inline void
228 _setLength(TraceSegment_<TPosition, TSize> & traceSegment, TSize newLength)
229 {
230     traceSegment._length = newLength;
231 }
232 
233 // ----------------------------------------------------------------------------
234 // Function _translateTraceValue()
235 // ----------------------------------------------------------------------------
236 
237 // Translates the trace value into a human-readable format.
238 //
239 // Note, used for debugging reasons only.
240 template <typename TTraceValue>
241 String<char> _translateTraceValue(TTraceValue const & traceValue)
242 {
243     String<char> transcript;
244 
245     if ((traceValue & TraceBitMap_<TTraceValue>::DIAGONAL) == TraceBitMap_<TTraceValue>::DIAGONAL)
246         append(transcript, 'D');
247     if ((traceValue & TraceBitMap_<TTraceValue>::VERTICAL) == TraceBitMap_<TTraceValue>::VERTICAL)
248         append(transcript, 'V');
249     if ((traceValue & TraceBitMap_<TTraceValue>::HORIZONTAL) == TraceBitMap_<TTraceValue>::HORIZONTAL)
250         append(transcript, 'H');
251     if ((traceValue & TraceBitMap_<TTraceValue>::VERTICAL_OPEN) == TraceBitMap_<TTraceValue>::VERTICAL_OPEN)
252         append(transcript, 'v');
253     if ((traceValue & TraceBitMap_<TTraceValue>::HORIZONTAL_OPEN) == TraceBitMap_<TTraceValue>::HORIZONTAL_OPEN)
254         append(transcript, 'h');
255     if ((traceValue & TraceBitMap_<TTraceValue>::MAX_FROM_VERTICAL_MATRIX) == TraceBitMap_<TTraceValue>::MAX_FROM_VERTICAL_MATRIX)
256         append(transcript, '|');
257     if ((traceValue & TraceBitMap_<TTraceValue>::MAX_FROM_HORIZONTAL_MATRIX) == TraceBitMap_<TTraceValue>::MAX_FROM_HORIZONTAL_MATRIX)
258         append(transcript, '-');
259 
260     if ((traceValue) == TraceBitMap_<TTraceValue>::NONE)
261         append(transcript, '0');
262     return transcript;
263 }
264 
265 // ----------------------------------------------------------------------------
266 // Function oerpator<<()
267 // ----------------------------------------------------------------------------
268 
269 template <typename TStream, typename TSize, typename TPosition>
270 TStream & operator<<(TStream & stream, TraceSegment_<TSize, TPosition> const & traceSegment)
271 {
272     stream << _translateTraceValue(traceSegment._traceValue) << "-";
273     stream << "(" << traceSegment._horizontalBeginPos << ", " << traceSegment._verticalBeginPos << ", " <<
274     traceSegment._length << ")";
275     return stream;
276 }
277 
278 // ----------------------------------------------------------------------------
279 // Function oerpator==()
280 // ----------------------------------------------------------------------------
281 
282 template <typename TPosition, typename TSize>
283 inline bool operator==(TraceSegment_<TPosition, TSize> const & left, TraceSegment_<TPosition, TSize> const & right)
284 {
285     if (left._horizontalBeginPos != right._horizontalBeginPos)
286         return false;
287 
288     if (left._verticalBeginPos != right._verticalBeginPos)
289         return false;
290 
291     if (left._length != right._length)
292         return false;
293 
294     if (left._traceValue != right._traceValue)
295         return false;
296 
297     return true;
298 }
299 
300 // ----------------------------------------------------------------------------
301 // Function oerpator!=()
302 // ----------------------------------------------------------------------------
303 
304 template <typename TPosition, typename TSize>
305 inline bool operator!=(TraceSegment_<TPosition, TSize> const & left, TraceSegment_<TPosition, TSize> const & right)
306 {
307     return !(left == right);
308 }
309 
310 // ----------------------------------------------------------------------------
311 // Function recordSegment()
312 // ----------------------------------------------------------------------------
313 
314 // Records a segment given the horizontal and vertical begin position, the length,
315 // and the corrsponding trace value.
316 //
317 // The first parameter is the container the segment is recorded to.
318 template <typename TTraceSegments, typename TPositionH, typename TPositionV, typename TSize, typename TTraceValue>
319 inline void _recordSegment(TTraceSegments & traceSegments,
320                            TPositionH const & horizontalBeginPos,
321                            TPositionV const & verticalBeginPos,
322                            TSize const & segmentLength,
323                            TTraceValue const & traceValue)
324 {
325     typedef typename Value<TTraceSegments>::Type TTraceSegment;
326 
327     if (segmentLength == 0)
328         return;  // we don't store empty segments
329 
330     if (traceValue & TraceBitMap_<TTraceValue>::DIAGONAL)
331         appendValue(traceSegments, TTraceSegment(horizontalBeginPos, verticalBeginPos, segmentLength, TraceBitMap_<TTraceValue>::DIAGONAL));
332     else if (traceValue & TraceBitMap_<TTraceValue>::VERTICAL)
333         appendValue(traceSegments, TTraceSegment(horizontalBeginPos, verticalBeginPos, segmentLength, TraceBitMap_<TTraceValue>::VERTICAL));
334     else if (traceValue & TraceBitMap_<TTraceValue>::HORIZONTAL)
335         appendValue(traceSegments, TTraceSegment(horizontalBeginPos, verticalBeginPos, segmentLength, TraceBitMap_<TTraceValue>::HORIZONTAL));
336     // everything else is not tracked.
337 }
338 
339 }  // namespace seqan
340 
341 #endif  // #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_DP_TRACE_SEGMENT_H_
342